それはリンクリストですか、配列ですか? 調べてみましたが、推測している人しか見つかりませんでした。私の C の知識はソースコードを見るには不十分です。
ベストアンサー1
Cコードは実はとてもシンプルです。マクロを1つ展開し、無関係なコメントを削除すると、基本的な構造は次のようになります。listobject.h
はリストを次のように定義します。
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;
PyObject_HEAD
参照カウントと型識別子が含まれています。つまり、これは過剰割り当てするベクトル/配列です。このような配列がいっぱいになったときにサイズを変更するコードは次のとおりです。listobject.c
配列を実際に2倍にするわけではなく、割り当てることで拡大します。
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
new_allocated += newsize;
毎回容量まで増加します。ここで、はnewsize
要求されたサイズです (要素を 1 つずつ増やす代わりに、任意の数の要素を追加allocated + 1
できるため、必ずしもそうとは限りません)。extend
append
以下も参照Python よくある質問。