先日以下のブログを読みました。
dev.classmethod.jp
PythonのListとDequeのパフォーマンスを比較しています。
しかし、「なぜパフォーマンスに違いが生まれるのか。」記されていないため、この記事ではCPythonの実装を読みながら、違いが生まれる理由を探ってみたいと思います。
※本記事で扱うCPythonのコードは最新版ではありません。
ListはCommit ID3c87a667bb367ace1de6bd1577fdb4f66947da52、DequeはCommit IDd4edfc9abffca965e76ebc5957a92031a4d6c4d4です。
目次
- List Objectについて
- Deque Objectについて
- List vs Deque（先頭要素)
3.1 List
3.2 Deque
3.3 まとめ(先頭要素)
- List vs Deque（中間要素)
4.1 List
4.2 Deque
4.3 まとめ(中間要素)
- List vs Deque（末端要素)
5.1 List
5.2 Deque
5.3 まとめ(末端要素)
- おわりに
- 参考文献
1. List Objectについて
初めに、簡単にデータ構造を整理しておきます。
Listは以下のようになっております。
typedef struct {
PyObject_VAR_HEAD
PyObject **ob_item;
Py_ssize_t allocated;
} PyListObject;
#ifndef PyList_MAXFREELIST
#define PyList_MAXFREELIST 80
#endif
static PyListObject *free_list[PyList_MAXFREELIST];
static int numfree = 0;
ob_itemがvectorへのポインタを指すことで、可変長データ構造を実現しています。
(Listをnew()する場合、free_listからPyListObjectを一つ取り出し、
メモリ確保しています。
op->ob_item = (PyObject **) PyMem_Calloc(size, sizeof(PyObject *));
)
https://github.com/python/cpython/blob/3c87a667bb367ace1de6bd1577fdb4f66947da52/Include/listobject.h
https://github.com/python/cpython/blob/3c87a667bb367ace1de6bd1577fdb4f66947da52/Objects/listobject.c
2. Deque Objectについて
Dequeは、双方向リンクリストと配列のハイブリッドで実現されています。
#define BLOCKLEN 64
#define CENTER ((BLOCKLEN - 1) / 2)
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;
static PyTypeObject deque_type;
#define MAXFREEBLOCKS 16
static Py_ssize_t numfreeblocks = 0;
static block *freeblocks[MAXFREEBLOCKS];
図で整理すると以下の通りです。(一部簡略)
https://github.com/python/cpython/blob/d4edfc9abffca965e76ebc5957a92031a4d6c4d4/Modules/_collectionsmodule.h
https://github.com/python/cpython/blob/d4edfc9abffca965e76ebc5957a92031a4d6c4d4/Modules/_collectionsmodule.c
3. List vs Deque（先頭要素)
参考ブログでは以下のコードで、処理時間を比較しています。
List
list_array = list(range(100000))
for i in range(1000):
list_array.pop(0)
処理時間は以下の通りです。
1回目 elapsed_time:0.05488991737365723[sec]
2回目 elapsed_time:0.04288434982299805[sec]
3回目 elapsed_time:0.054895877838134766[sec]
Deque
deque_array = deque(range(100000))
for i in range(1000):
deque_array.popleft()
処理時間は以下の通りです。
1回目 elapsed_time:0.008365631103515625[sec]
2回目 elapsed_time:0.007332801818847656[sec]
3回目 elapsed_time:0.008947134017944336[sec]
3.1. List
List.pop()の実装部はここです。
エラーチェック後、実質的にpop処理をしているのは以下の部分です。
status = list_ass_slice(self, index, index+1, (PyObject *)NULL);
pop(0)の場合、以下のようになります。
ex: a = [1,2,3,4,5,6,7,8,9,10]
list_ass_slice(self, 0, 1, (PyObject *)NULL);
#define b ((PyListObject *)v)
if (v == NULL)
n = 0;
norig = ihigh - ilow; // 1
d = n - norig; // -1
item = a->ob_item;
s = norig * sizeof(PyObject *); // sizeof(PyObject *)
if (s) {
memcpy(recycle, &item[ilow], s);
}
if (d < 0) { /* Delete -d items */
Py_ssize_t tail;
tail = (Py_SIZE(a) - ihigh) * sizeof(PyObject *); // 9 * sizeof(PyObject *)
memmove(&item[ihigh+d], &item[ihigh], tail); // a[1:10] を a[0:9]に移動
if (list_resize(a, Py_SIZE(a) + d) < 0) { // Py_SIZE(a)の変更
}
item = a->ob_item;
}
for (k = norig - 1; k >= 0; --k)
Py_XDECREF(recycle[k]); // ref--
result = 0;
決めては以下の処理。
memmove(&item[ihigh+d], &item[ihigh], tail); // a[1:10] を a[0:9]に移動
計算量がO(n)であることが分かります。
3.2. Deque
deque.leftpop()の実装部はここです。
サイズチェック後、実質的にpop処理をしているのは以下の部分です。
item = deque->leftblock->data[deque->leftindex];
deque->leftindex++;
Py_SIZE(deque)--;
計算量がO(1)であることが分かります。
3.3. まとめ(先頭要素)
先頭要素への処理の計算量は以下の通りです。
| 処理 |
計算量 |
| List.pop(0) |
O(1) |
| Deque.leftpop() |
O(n) |
4. List vs deque（中間の要素）
参考ブログでは以下のコードで、処理時間を比較しています。
List
list_array = list(range(10000))
for i in range(1000000):
list_array.remove(20)
list_array.insert(20, 20)
処理時間は以下の通りです。
1回目 elapsed_time:25.979241132736206[sec]
2回目 elapsed_time:26.479660749435425[sec]
3回目 elapsed_time:26.32246232032776[sec]
Deque
deque_array = deque(range(10000))
for i in range(1000000):
deque_array.remove(20)
deque_array.insert(20, 20)
処理時間は以下の通りです。
1回目 elapsed_time:21.0693142414093[sec]
2回目 elapsed_time:21.471088647842407[sec]
3回目 elapsed_time:21.121334075927734[sec]
4.1. List
Listのremoveの実装はここです。
中身の肝は以下。
list_ass_slice(self, i, i+1, PyObject *)NULL)
popと同様に計算量がO(n)であることが分かります。
Listのinsertの実装はここです。
中身の肝は以下。
ins1(self, index, object)
insert(20,20)の場合、以下のようになります。
ex: a = [0,...,19,21...,100000]
ins1(self, 20, 20)
Py_ssize_t i, n = Py_SIZE(self); // 99,999
if (list_resize(self, n+1) < 0) // Py_SIZE(self)++
items = self->ob_item;
for (i = n; --i >= where; )
items[i+1] = items[i];
Py_INCREF(v);
items[where] = v;
計算量がO(n)であることが分かります。
4.2. Deque
dequeのremoveの実装はここです。
中身の肝は以下。
for (i=0 ; i<n ; i++) {
PyObject *item = deque->leftblock->data[deque->leftindex];
int cmp = PyObject_RichCompareBool(item, value, Py_EQ);
if (cmp > 0) {
PyObject *tgt = deque_popleft(deque, NULL);
assert (tgt != NULL);
if (_deque_rotate(deque, i))
return NULL;
Py_DECREF(tgt);
Py_RETURN_NONE;
}
_deque_rotate(deque, -1);
}
要素判定は常に左端要素を使用します。要素が見つかるまでrotate(-1)を行います。要素が見つかり次第、popleft()し、rotate(要素index)します。
計算量がO(n)であることが分かります。
この_deque_rotate()の中身はここです。
中身の肝は以下。
Py_ssize_t m = n;
if (m > rightindex + 1)
m = rightindex + 1;
if (m > leftindex)
m = leftindex;
assert (m > 0 && m <= len);
rightindex -= m;
leftindex -= m;
src = &rightblock->data[rightindex + 1];
dest = &leftblock->data[leftindex];
n -= m;
do {
*(dest++) = *(src++);
} while (--m);
deque->leftblock = leftblock;
deque->rightblock = rightblock;
deque->leftindex = leftindex;
deque->rightindex = rightindex;
計算量がO(n)であることが分かります。
次にinsertの実装はここです。
中身の肝は以下。
if (_deque_rotate(deque, -index))
return NULL;
if (index < 0)
rv = deque_append(deque, value);
else
rv = deque_appendleft(deque, value);
if (_deque_rotate(deque, index))
return NULL;
rotate()して左端か右端にappend()しています。
rotate()の計算量は上記の通り、O(n)であることが分かります。
4.3. まとめ(中間要素)
中間要素への処理の計算量は以下の通りです。
| 処理 |
計算量 |
| List.remove() |
O(n) |
| List.insert() |
O(n) |
| Deque.remove() |
O(n) |
| Deque.insert() |
O(n) |
参照ブログでは、Dequeの方が高速に処理できました。
その理由は、以下の通りです。
List: 削除要素以外の全要素でメモリ移動が伴う
Deuqe: 先頭要素から削除要素までのみメモリ移動が伴う
処理時間測定コードでは、先頭から20番目の要素をromove()、insert()しています。よってDequeの方が、メモリ移動の対象になる要素が少なく、処理時間が高速だったと考えられます。
5. List vs deque（末端の要素）
参考ブログでは以下のコードで、処理時間を比較しています。
List
list_array = list(range(1000))
for i in range(100000):
list_array.append(0)
処理時間は以下の通りです。
1回目 elapsed_time:0.017949581146240234[sec]
2回目 elapsed_time:0.019548416137695312[sec]
3回目 elapsed_time:0.019548416137695312[sec]
Deque
deque_array = deque(range(1000))
for i in range(100000):
deque_array.append(0)
処理時間は以下の通りです。
1回目 elapsed_time:0.023968935012817383[sec]
2回目 elapsed_time:0.023933887481689453[sec]
3回目 elapsed_time:0.01991128921508789[sec]
5.1. List
Listのappendの実装はここです。
中身の肝は以下。
app1(self, object)
append(0)の場合、以下のようになります。
Py_ssize_t n = PyList_GET_SIZE(self);
if (list_resize(self, n+1) < 0) // Py_SIZE(self)++
Py_INCREF(v);
PyList_SET_ITEM(self, n, v); // (((PyListObject *)(op))->ob_item[i] = (v))
計算量がO(1)であることが分かります。
5.2. Deque
dequeのappendの実装はここです。
中身の肝は以下。
deque_append_internal(deque, item, deque->maxlen)
deque_append_internal()の実装はここです。
中身の肝は以下。
deque->rightindex++;
deque->rightblock->data[deque->rightindex] = item;
計算量がO(1)であることが分かります。
5.3. まとめ(末端要素)
末尾要素への処理の計算量は以下の通りです。
| 処理 |
計算量 |
| List.append() |
O(1) |
| Deque.append() |
O(1) |
6. おわりに
本記事では、PythonのListとDequeの処理の違いをCythonのコードから探ってみました。
ListとDequeによって「なぜパフォーマンスに違いが生まれるのか。」理解につながれば幸いです。
7. 参考文献
https://postd.cc/python-internals-pyobject/
https://note.nkmk.me/python-collections-deque/
https://docs.python.org/ja/3/c-api/sequence.html
https://docs.python.org/ja/3/c-api/intro.html
https://docs.python.org/3/c-api/typeobj.html
