Python のリストはリンクされたリストとして実装されていますか? それとも配列として実装されていますか?

Python リストの実装が公開されました

リンクされたリストですか、それとも配列ですか?

Python のリスト操作の領域では、基礎となる実装は多くの人にとって謎のままです。憶測はたくさんありますが、具体的な答えは好奇心をそそられません。この謎を明らかにするために、C コードを詳しく調べて、Python のリスト構造の本質を明らかにします。

ポインターのベクトル

推測に反して、リンク リストと同様に、Python のリストは配列のような構造に基づいて構築されます。 listobject.h ヘッダーを調べると、リストの中核となる定義、つまり PyListObject と呼ばれる型が明らかになります。この構造は 3 つの必須要素で構成されます。

• ob_size: 現在使用されている要素の数。
• ob_item: Python オブジェクトの配列リストを表すポインターitems.
• allocated: 配列の最大容量。

動的割り当てと過剰割り当て

配列ob_item は、C の配列と同様に、リスト要素への直接アクセスを提供します。ただし、Python は次の戦略を採用しています。効率を最適化するための過剰割り当て。 ob_item 配列が容量いっぱいになると、より大きな新しい配列が割り当てられます。新しい容量は次の式を使用して計算されます。

new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
new_allocated += newsize;

ここで、newsize は要求されたサイズです。この式により、過度の割り当てオーバーヘッドを回避しながら、今後の挿入に十分なスペースが確保されます。

結論

Python のリスト インターフェイスの背後には、ベクトルベースの実装があります。各リスト項目はオブジェクトへのポインターによって表され、ベクトル自体はパフォーマンスを向上させるために動的に割り当てられたり、過剰に割り当てられたりします。このアプローチは、効率的なストレージと柔軟な拡張のバランスをとり、Python の必須リスト データ構造のシームレスな操作を可能にします。

以上がPython のリストはリンクされたリストとして実装されていますか? それとも配列として実装されていますか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。