Python は内部でリストをどのように実装するのでしょうか?

Python リストの実装: 謎を解く

Python リストは、言語の不可欠な側面であり、あらゆる型の要素のコレクションを格納します。多くの開発者がその基本的な実装について推測してきましたが、決定的な答えは依然として得られていません。この記事では、Python の C コードを深く掘り下げて、リスト実現の背後にある真実を明らかにします。

ヘッダー ファイル listobject.h を調べると、Python リストの基本構造がわかります。

typedef struct {
    PyObject_HEAD
    Py_ssize_t ob_size;

    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
    PyObject **ob_item;

    /* ob_item contains space for 'allocated' elements.  The number
     * currently in use is ob_size.
     * Invariants:
     *     0 ≤ ob_size ≤ allocated
     *     len(list) == ob_size
     *     ob_item == NULL implies ob_size == allocated == 0
     */
    Py_ssize_t allocated;
} PyListObject;

このコードは、Python リストが実際にベクトルまたは配列として実装されていることを示しています。具体的には、過剰割り当て戦略を利用します。これは、リストへの追加の可能性のためにメモリが事前に割り当てられることを意味します。

リストが割り当てられた制限に達すると、listobject.c のサイズ変更コードが以下を割り当てて配列を拡張します。

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

ここで、newsize は、任意の数の要素で拡張するか、単に追加するかに関係なく、要求されたサイズを表します。 one.

さらに、Python FAQ ではリストの実装に関する追加の洞察が提供され、パフォーマンスを維持しながら必要に応じてサイズを変更できる動的で効率的な性質が強調されています。

以上がPython は内部でリストをどのように実装するのでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。