Python3のdequeの実装を調べる:

この問題で、Pythonのdequeのindexed参照が$O(N)$なんだ！というポストをみかけました。Pythonのdequeの実装はどうなっているのでしょうか？以下はPython-3.8.10.tar.gzのコードから参照します。

冒頭のコメントを読む(日本語のみ)

• dequeの特徴はappendやpopにおいて操作するデータ以外の位置を移動させないことだ。加えて、(全体に対する)reallocを発生させない
• Pythonのdequeは固定ブロックサイズのダブルリンクドリストに格納される。これは一般のリンクドリストは１つの要素ごとにnxt/prvをもったりして非効率的だから。また、連続アクセスのキャッシュ局所性への対応も実現する。

ダブルリンクドリストのイメージとdequeの構造体の実装

以下はイメージです。各要素は前後の要素へのポインタを持ちます。各要素は要素のデータを持ちます。

実装を見ます。

• 上(block)は各要素のブロックのオブジェクト。これは教科書的な実装。left=prev, right=nextと考えればよい。
• 下(dequeobject)がdeque自身の親オブジェクト

Modules/_collectionsmodule.c

typedef struct BLOCK {
    struct BLOCK *leftlink;
    PyObject *data[BLOCKLEN];
    struct BLOCK *rightlink;
} block;

typedef struct {
    PyObject_VAR_HEAD
    block *leftblock;
    block *rightblock;
    Py_ssize_t leftindex;       /* 0 <= leftindex < BLOCKLEN */
    Py_ssize_t rightindex;      /* 0 <= rightindex < BLOCKLEN */
    size_t state;               /* incremented whenever the indices move */
    Py_ssize_t maxlen;          /* maxlen is -1 for unbounded deques */
    PyObject *weakreflist;
} dequeobject;

dequeの添え字アクセス

参照はdeque_item, 変更はdeque_ass_itemで行われます。ここではdeque_itemのみを見ましょう。必要そうな場所だけ抜粋します。
※エラー処理、左右の添え字アクセスの時の例外処理を割愛しています

Modules/_collectionsmodule.c

deque_item(dequeobject *deque, Py_ssize_t i)
{
    i += deque->leftindex;
    // (1): n, iの計算
    n = (Py_ssize_t)((size_t) i / BLOCKLEN);
    i = (Py_ssize_t)((size_t) i % BLOCKLEN);
    printf("[%d] : target block-index = %d-%d\n", index, (int)n, i); // デバッグ用に追加
    // (2-1): 次のifは右から辿るのが早いか、左に辿るのが早いかで分岐する。
    if (index < (Py_SIZE(deque) >> 1)) {
        b = deque->leftblock;
        while (--n >= 0) // (2-2): n回右に辿る
            printf(" search...\n"); // デバッグ用に追加
            b = b->rightlink;
    } else {
        n = (Py_ssize_t)(
                ((size_t)(deque->leftindex + Py_SIZE(deque) - 1))
                / BLOCKLEN - n);
        b = deque->rightblock;
        while (--n >= 0) // (2-2): n回「左」に辿る
            printf(" search...\n");// デバッグ用に追加
            b = b->leftlink;
    }
    return b->data[i];
}

このコードは以下のように動作します。

• 与えられた[i]から何個目のブロック(n)であるかと、そのブロックの何個目のindex(i)であるかを計算します
• そのnは右から(先頭から)辿るのが早いか、左(後ろから)辿るのが早いかを判定します。dequeの先頭からlen-n回その方向に辿って、そのstruct blockを返します。
• return block->data[i]します。

はさみこんだprintf debugでの例

以下を実行します。[0] - [999]の100個のdequeの要素を作り、(printfによって)それぞれのブロックの位置と、そのブロックを探すために何回の辿りが発生したかを表示できます。

import collections
d = collections.deque()
for i in range(1000): d.append(i)
for i in range(100): d[i]
d[500]
for i in range(900,1000): d[i]

以下の結果が得られます。

./configure
make
./python < a.py
-----
[1] : target block-index = 0-33
[2] : target block-index = 0-34
[3] : target block-index = 0-35
 ...(略)...
[31] : target block-index = 0-63
[32] : target block-index = 1-0
 search...
[33] : target block-index = 1-1
 search...
 ...(略)...
[95] : target block-index = 1-63
 search...
[96] : target block-index = 2-0
 search...
 search...
[97] : target block-index = 2-1
 search...
 search...
 ...(略)...
 [500] : target block-index = 8-20
 search...
 search...
 search...
 search...
 search...
 search...
 search...
 search...
 ...(略)...
 [991] : target block-index = 15-63
 search...
[992] : target block-index = 16-0
[993] : target block-index = 16-1
[994] : target block-index = 16-2
[995] : target block-index = 16-3
[996] : target block-index = 16-4
[997] : target block-index = 16-5

次のようなことが言えます。

• [0]へのアクセスは特殊に扱われているので(現コードを見てください)今回のコードではprintfされません
• [1]へのアクセスがindex=33から始まっています。これはappendleftを見越して(だと思うのですが) deque_new()内でdeque->leftindex = CENTER + 1とindexを0からではなく、真ん中から始めています
• [0]がindex=32からの開始なので、[31]はブロック0のindex 63でブロックの端に来ています。このため、[32]へのアクセスはブロック1になり、search...というように次のblockを辿ったことが分かります。
• [500]へのアクセスは9個目のblockへのアクセスなのでsearch...が8回出力されています。これがdequeの添え字アクセスに$O(N)$かかる理由です。
• 逆に[991]は1回だけ、[992]以上の添え字へのアクセスは0回の辿りであることに注意してください。これは(3)で述べたようにindex < (Py_SIZE(deque) >> 1)にて半分より後のアクセスの場合は後ろから辿っているためです。

まとめ

• dequeへの参照・更新アクセスは[i]に対するアクセスの際、i / BLOCK_LEN(標準では64) / 2のアクセスが必要。ただし、結果として時間計算量は$O(N)$で変わらない。
  • 特徴1: 1要素ごとにリンクドリストの要素を作るのではなく、BLOCK_LEN個まとめたブロックを使う
  • 特徴2: 前後どちらから辿るのが早いかを考えて計算する。(/2の理由)