私がプログラミングを学んでいたとき、Python のリストは私にとって完全に魔法のように思えました。 私は、一部はリンクリスト、一部は配列で、すべてに完璧な、ある種の魔法のようなデータ構造によって実装されていると想像していました。 ある種の魔法のような実装ではなく、サイズ変更可能な配列によってバックアップされているだけだと (正しく) 推測しました。

CPython の良いところの 1 つは、読みやすい実装であることです。 関連するファイルは 2000 行以上の C 言語ですが、そのほとんどはソート アルゴリズムと Python コードから関数を呼び出せるようにするための定型文です。

以下は、私が実装を読んで見つけたいくつかの興味深い点です。

List Resizing

Python のリストに追加する際、バック配列が十分に大きくない場合、バック配列を拡張する必要があります。 このとき、バックアレイは約12%拡大されます。 個人的には、この成長率はもっと大きいと思っていました。 Java では ArrayList は拡張されると 50% 成長し2、Ruby では Array は 100% 成長します3

// essentially, the new_allocated = new_size + new_size / 8new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);

link to CPython reallocation code

I did a few performance experiments – preallocating array with constructs like *500 does not seem to make any noticeable difference. 1億回リストに追加するという私の非科学的ベンチマークでは、Python 3 は Python 2 よりもずっと遅く、Ruby よりもずっと遅かったです。しかし、挿入パフォーマンスに対する成長因子の影響（もしあれば）を判断するには、もっとたくさんの研究が必要です。

Inserting at the beginning of the list

Inserting at the beginning of a list takes linear time – これは残りの実装を考えるとそれほど驚くことではありませんが、some_list.insert(0,value) が良いアイディアではないことは知っておくとよいでしょう。 Reddit ユーザーは、一定時間のインデックス作成と引き換えに、両端からの一定時間の挿入と削除を交換する Deques を私に思い出させました。 some_list はスライスのサイズに対して線形時間操作なので、やはり魔法ではありません。 ある種のコピーオンライトのセマンティクスでこれを最適化することも考えられますが、CPython のコードは単純であることを優先しています。 これはプロのPython開発者の間では一般的に知られていると思いますが、私は数年間のPythonプログラミングで一度も遭遇したことがありません。コード内のlist_ass_slice(...)関数に出くわして初めて発見しました。 しかし、大きなリストでは注意が必要です – 元のリストから削除されたすべてのアイテムをコピーする必要があり、メモリ使用量が簡単に倍増します。

>>> a = >>> a = 'a'>>> a>>> a = >>> a = >>> a

Sorting

Python 配列は “timsort” として知られているアルゴリズムでソートされています。 これは非常に複雑で、ソースツリーのサイドドキュメントに詳細が記述されています。 大雑把に言うと、連続した項目をどんどん長くしていき、それらをマージしていくものです。 通常のマージソートとは異なり、すでにソートされているリストのセクションを探すことから始まります (コード中の runs)。 これにより、すでに部分的にソートされた入力データを利用することができます。面白い話があります。 興味深いことに、64要素までの小さな配列（あるいは大きな配列の小さなセクション）をソートする場合4、timsortは「バイナリソート」を使用します。 これは本質的には挿入ソートですが、正しい位置に要素を挿入するためにバイナリサーチを使用します。 これは実際には O(n^2) アルゴリズムです。 実際のところ、アルゴリズムの複雑さよりも実際のパフォーマンスが勝っているという興味深い例です。 link

CPython のリストについて何かクールなことを見逃していませんか？

Thanks to Leah Alpert for providing suggestions on this post.

Want to get email about new blog posts?

I post about once every few weeks on topics likedatabases, language internals and algorithms, and recently, deep learning.Do you want to hire me? 1週間から数ヶ月の契約は可能です。 雇ってください。