今日も窓辺でプログラム

外資系企業勤めのエンジニアが勉強した内容をまとめておくブログ

Pythonのlist型の実装を読んでみる

Python

この記事を読むとわかること

Pythonのリスト型の実装に軽く目を通してみます。この記事で、次のような疑問が解消されるはずです。

  1. Pythonのリスト型は実際はどのような形で定義されているのか？
  2. リストの要素へのインデックスでのアクセスはなぜ O(1)なのか？
  3. リストの要素へのスライスでのアクセスはなぜ O(k)なのか？

記事が長いので短い回答も用意しておきます。

  1. C言語の配列
  2. C言語の配列へのランダムアクセスだから
  3. C言語の配列のk個の要素を新しい配列にコピーしているから

目次

きっかけ

最近、某Online Judgeのサイトでコードを書くときにPythonを使っているのですが、今までなんとなくPythonを使っていただけで詳しい実装とか勉強したことなかったな、と思ったのでコードを読んでみることにしました。
例えば、Pythonのリストの n番目のアクセスにかかる時間って O(1) か O(n) かわかりますか？リストって名前だし、 O(n)？いやいや、さすがにそのままリストを実装してるわけじゃなくて、ランダムアクセスは O(1)になってるんじゃないの？
…このような感じで、実際に何にどのくらいの処理がかかるか自信をもって答えられなかったので、内部を見てみようと思ったわけです。

対象の実装

この記事では、Pythonの最も標準的な実装であるCPythonのソースコードを読んでいきます。
CpythonはC言語で実装されており、ソースコードは以下で公開されています。
https://svn.python.org/projects/python/trunk/
Githubにread-onlyのミラーも存在しているようなので、そちらの方が使い勝手がいいかも。
GitHub - python/cpython: The Python programming language

リストの実装

ソースコードの場所

まずはリスト型の実装を見ていきます。
4. 組み込み型 — Python 3.6.5 ドキュメント

リスト型とは、配列のように使用される、このようなデータ型のことです。

a = [1, 2, 3, 4, 5]

リストの実装は以下の場所で公開されています。
ヘッダ：cpython/listobject.h at master · python/cpython · GitHub
コード：cpython/listobject.c at master · python/cpython · GitHub

また、時間計算量は次のページで紹介されています。
TimeComplexity - Python Wiki

コードを開いてみると、大体3000行のコードの中にリスト型の操作が定義順にされています。まずはメモリの確保・解放がどのように行われているのか、リスト型は内部的にはどのような扱いになっているのかを見てみたいと思います。

PyObject, PyVarObject構造体

リストの定義を見る前に、PyObject構造体について知っておく必要があります。Pythonのすべてのオブジェクトは、PyObject構造体の拡張として実装される必要があります。
PyObject構造体には、オブジェクトへのポインタと参照カウントが定義されているようです。Pythonのオブジェクトを参照するときは、このPyObjectへのポインタ(= PyObject*)参照を使用しなくてはなりません。詳細は省略しますが、興味のある方は以下のコードで定義を読むことができます。
cpython/object.h at master · python/cpython · GitHub

また、PyVarObject構造体というものも存在します。これはPyObject構造体を拡張したもので、オブジェクトへのポインタ、参照カウントに加えてオブジェクトのサイズを保持しています。リスト型など、オブジェクトサイズが可変の場合にはこの構造体を用いるようです。

リスト型の定義

ヘッダファイルを開いてみると、リスト型 PyListObject が次のように定義されています。

typedef struct {
    PyObject_VAR_HEAD
    /* 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
     * list.sort() temporarily sets allocated to -1 to detect mutations.
     *
     * Items must normally not be NULL, except during construction when
     * the list is not yet visible outside the function that builds it.
     */
    Py_ssize_t allocated;
} PyListObject;

構造体の最初に記述されている PyObject_VAR_HEAD というのは、PyVarObject構造体を定義するためのマクロです。先ほど説明した通り、すべてのPythonオブジェクトはPyObject構造体をもとにしていなければいけません。

PyVarObject ob_base;

次に ob_item という PyObject（へのポインタのポインタ）が定義されていて、これがリスト本体になります。つまり、リスト型の実体はC言語の配列です。リストの0番目の要素はob_itemの0番目の要素 (= ob_item[0])になります。

3番目のPy_ssize_t型のallocatedという変数は、現在メモリ上に確保されている領域の要素数を保持しています。例えば、10個分の領域が確保されていたら、allocatedは10にセットされます。

また、せっかくヘッダファイルを見ているので、一緒に定義されているマクロも確認しておきましょう。
要素のGET/SET、そしてリストのサイズを取得するマクロが次のように定義されています。

#define PyList_GET_ITEM(op, i) (((PyListObject *)(op))->ob_item[i])
#define PyList_SET_ITEM(op, i, v) (((PyListObject *)(op))->ob_item[i] = (v))
#define PyList_GET_SIZE(op)    Py_SIZE(op)

先ほど見た通りob_itemのi番目の要素(= ob_item[i])の値を読んだり書いたりしているだけです。これらのマクロを経由してリストの値が読み書きされているなら、C言語の配列へのランダムアクセスなので O(1)の時間しかかからないことになりそうですね。
また、PyList_GET_SIZEはPyVarObject構造体から現在のオブジェクトのサイズを取り出すマクロです。

#define Py_SIZE(ob)             (((PyVarObject*)(ob))->ob_size)

ですので、このマクロも O(1)の時間で処理されます。

リスト型の要素のアクセス

リストの要素へのアクセスはどのように処理されるのでしょうか。list[i]のように、インデックスを使用してアクセスした場合、list.__getitem__メソッドが呼ばれます。listobject.cには次のような定義が存在します。どうやら、__getitem__というメソッドは、list_subscriptという関数に結び付けられているようです。

static PyMethodDef list_methods[] = {
    {"__getitem__", (PyCFunction)list_subscript, METH_O|METH_COEXIST, getitem_doc},
    {"__reversed__",(PyCFunction)list_reversed, METH_NOARGS, reversed_doc},
    {"__sizeof__",  (PyCFunction)list_sizeof, METH_NOARGS, sizeof_doc},
    // 省略
};

list_subscriptはlistobject.cで実装されています。引数selfはリストオブジェクト、itemはインデックスやスライスなどリストの対象要素を指定するためのオブジェクトです。この関数の大枠は次のようになっています。

static PyObject *
list_subscript(PyListObject* self, PyObject* item)
{
    if (PyIndex_Check(item)) {
        // インデックスを使ったアクセスの処理
    }
    else if (PySlice_Check(item)) {
        // スライスを使ったアクセスの処理
    }
    else {
        // 不正な要素指定なのでエラー処理
    }
}
インデックスを使ったアクセスの処理

PyIndex_Check(item)は、おそらく正しいインデックスが与えられた場合にTrueとなります。
ではその場合にはどのような処理が行われるのでしょうか。

        Py_ssize_t i;
        i = PyNumber_AsSsize_t(item, PyExc_IndexError);
        if (i == -1 && PyErr_Occurred())
            return NULL;
        if (i < 0)
            i += PyList_GET_SIZE(self);
        return list_item(self, i);

与えられたインデックスが0以上要素数未満だった場合は、そのインデックスをそのまま使用します。与えられたインデックスが負だった場合は、リストの長さを足してインデックスを正の数に変換します。PYList_GET_SIZEは定数時間で実行できたので、この部分も O(1)となります。そして最後にlist_itemという関数で要素を取り出しているようです。

static PyObject *
list_item(PyListObject *a, Py_ssize_t i)
{
    if (i < 0 || i >= Py_SIZE(a)) {
        if (indexerr == NULL) {
            indexerr = PyUnicode_FromString(
                "list index out of range");
            if (indexerr == NULL)
                return NULL;
        }
        PyErr_SetObject(PyExc_IndexError, indexerr);
        return NULL;
    }
    Py_INCREF(a->ob_item[i]);
    return a->ob_item[i];
}

インデックスが正しい範囲かを確認し（よく見るエラーメッセージはここで定義されてたんですね）、参照カウントを増やしたあとでPyListObjectのob_item[i]の値を返しています。これもC言語の配列へのランダムアクセスなので O(1)です。
つまり、インデックスを指定して要素にアクセスする場合は、 O(1)の時間で処理をすることができます。

スライスを使ったアクセスの処理

一部しかソースコードは引用しませんが、スライスの処理の核の部分はこのようになっています。

        if (slicelength <= 0) {
            return PyList_New(0);
        }
        else if (step == 1) {
            return list_slice(self, start, stop);
        }
        else {
            result = PyList_New(slicelength);
            if (!result) return NULL;

            src = self->ob_item;
            dest = ((PyListObject *)result)->ob_item;
            for (cur = start, i = 0; i < slicelength;
                 cur += (size_t)step, i++) {
                it = src[cur];
                Py_INCREF(it);
                dest[i] = it;
            }

            return result;
        }

まず一番下のelse節、stepが1ではないときは、新しいリストを用意してあげて、単純にそこに要素を詰め込んであげていますね。
stepが1の場合はそのままlist_sliceという関数に投げています。

static PyObject *
list_slice(PyListObject *a, Py_ssize_t ilow, Py_ssize_t ihigh)
{
    PyListObject *np;
    PyObject **src, **dest;
    Py_ssize_t i, len;
    if (ilow < 0)
        ilow = 0;
    else if (ilow > Py_SIZE(a))
        ilow = Py_SIZE(a);
    if (ihigh < ilow)
        ihigh = ilow;
    else if (ihigh > Py_SIZE(a))
        ihigh = Py_SIZE(a);
    len = ihigh - ilow;
    np = (PyListObject *) PyList_New(len);
    if (np == NULL)
        return NULL;

    src = a->ob_item + ilow;
    dest = np->ob_item;
    for (i = 0; i < len; i++) {
        PyObject *v = src[i];
        Py_INCREF(v);
        dest[i] = v;
    }
    return (PyObject *)np;
}

やっていることはすごく単純で、新しいリスト(= np)を用意して、そこにスライスの始点(=ilow)から終点(=ihigh)まで順に値をコピーしています。stepが1でないときと同様ですね。

つまり、スライスの長さが kの場合、スライスでの要素へのアクセスは O(k)の時間を要することになります。

まとめ

今回は、次のようなことが分かりました。

  • PythonのすべてのオブジェクトはPyObject構造体を拡張する形で定義されている
  • リスト型は、C言語の配列として定義されている
  • リストへのインデックスを使ったアクセスは、配列へのランダムアクセスとなるので O(1)の時間で終わる
  • リストへのスライスを使ったアクセスは、 k (=スライスの長さ)個の要素を新しい配列にコピーするので O(k)の時間がかかる

リストに定義されている他のメソッドや他の型についても、時間のある時に見ていけるといいなと考えています。