はじめに

Qiitaはよく利用するんですが、なにげ初投稿です！はじめまして！

Pythonの有益な記事はたくさんありますが、あまりPythonの内部の実装に触れてる記事は少ない印象なので、いろんなデータ構造の解説を内部実装と絡めてできたらいいなーっていうモチベーションです。
今回はPythonのlistについて書きます。

本記事について

Pythonのlistの仕組みについて書いた記事です。
けどリストの全てのメソッドについてどう動いてるとか書くのは無理なので主に

• リストってどういうデータ構造？配列じゃないの？
• リスト型の内部の実装はどうなっているの？
• 可変長配列って何？どういう規則でサイズ変えてるの？

などの疑問を解消できるような記事を書きました。

※実行環境のPythonのVersion: 3.8.0
※この記事の「Python」とは「CPython」のことを指しています。

対象読者

• 上記の疑問を持っている人
• Python入門本やチュートリアル等を読んでもう少し詳しく知りたい人
• 詳しく知りたいが公式ドキュメントとかcpythonコード読むのはめんどくさい人

データ構造

Pythonのlist型とはどういうデータ構造なのかを見ていきます。

おさらい

リストとは

>>> x = [1,2,3]
>>> x.append(4)
>>> x
[1, 2, 3, 4]

おなじみのこれです。

x.sort()
x.append(element)
x.clear()
x.extend(element)
x.index(element)
x.insert(element)
x.pop()
x.remove(element)
x.reverse()

このようなたくさんのメソッドがあります(雑)。

連結リストと配列

基本的な話なので知ってる人は飛ばしてください

配列は

• メモリ上の連続した領域を確保し、そこに要素を入れていく
• 要素へのアクセスにO(1),要素の挿入や削除にO(N)の時間がかかる

連結リスト(単方向)は

• 1つのノードは要素と次の要素へのポインタをもつ
• 要素へのアクセスにO(N),要素の挿入や削除にO(1)の時間がかかる

という特徴があります。

list のデータ構造

listは標準で使えるデータ構造でシーケンス型のうちの1つです。リストという名前をしているので連結リストを使って実装されていると思う人もいると思いますがPythonのリストは可変長配列(動的配列)として実装されています。つまりPythonのlistは配列です。名前紛らわしい。。

リストは他のオブジェクトへの参照を持った連続した配列です。リスト先頭の構造体(PyListObject)がこの配列へのポインタと長さを持っています。
実際にcpythonのコードを見てみると(Include/cpython/listobject.h)(コメント省略)

typedef struct {
    PyObject_VAR_HEAD
    PyObject **ob_item;
    Py_ssize_t allocated;
} PyListObject;

こんな感じに定義されてます。
リストはPyListObject、リスト内の要素はPyObjectという型で、内部では表現されています。
(PyObjectは全てのPythonオブジェクト型の基本となる型です。)
ob_itemはリスト内の要素のポインタの配列、allocatedは割り当てられたサイズです。

要素はPyObjectであればいいので、異なるデータ型の要素も同じリストに持つことができます。

x = [1,"a",[1,2,3]]

可変長配列

Pythonのlistは可変長配列だよという話をしました。
可変長配列では要素の追加や削除がされると参照している配列のサイズを変更します。ただ、毎回配列の大きさを変更するわけではありません。いい感じに,サイズを大きくするタイミングとその大きさを決めてます。

サイズの変更

新たに要素を加えるために配列のサイズを変えるときの処理は以下のようになります。

空き領域がなかったら新たな領域を確保し、現在の全ての要素をコピーし、新しい要素を追加します。

growth factor

配列がいっぱいになった時どのくらい拡大させるかはgrowth factor(既存の配列のサイズのだいたい何倍にするか)によって決まります。growth factorは言語によって異なります。(例えばPythonは1.125,Cは2です)

例えばgrowth factorが2とした時、配列に順番に要素を追加していくとサイズ(キャパシティ)は以下のようになります。

要素の削除の場合においても拡大と似たような縮小をします。

計算量

配列を拡大する操作は、全ての要素をコピーするので現在の要素数をkとした時、計算量はO(k)となります。

ここでlist.append(element)の計算量がO(1)となることについて考えます。
結論ならし計算量を考えるとこれはO(1)になります。

空の配列にn個の要素を順番に追加していく時、growth factorを2とすると計算量は

\begin{align}
O(n+2+2^2+2^3+\cdots+2^{logn}) \\
= O(n+2\times2^{logn})\\
= O(n)
\end{align}

となるのでn個の要素を追加する時の計算量はO(n)です。
よってlist.append(element)の計算量はO(1)になります。

実装を見る

Pythonのgrowth factorは1.125ですが具体的な拡大の仕方を見ていきます。
listに関する操作はObjects/listobject.cに書かれています。
リサイズする関数の重要なところを取り出すと以下のようになります。

static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
    /* This over-allocates proportional to the list size, making room
     * for additional growth.  The over-allocation is mild, but is
     * enough to give linear-time amortized behavior over a long
     * sequence of appends() in the presence of a poorly-performing
     * system realloc().
     * Add padding to make the allocated size multiple of 4.
     * The growth pattern is:  0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...
     * Note: new_allocated won't overflow because the largest possible value
     *       is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.
     */
    new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;
}

    new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;

なんか後半のマスク演算がわかりにくいですね笑

要は今のサイズを$\frac{9}{8}$倍してちょっと足してますね〜。確かにgrowth factorは1.125になってます。

まとめ

• Pythonのlistは配列である
• listは内部ではPyListObjectという型であり、PyObjectたちへのポインタを持っている。
• Pythonのgrowth factorは1.125

参考文献

• cpythonのgitリポジトリ
• python日本語ドキュメント
• エキスパートPythonプログラミング