[解決済み] deque.popleft()とlist.pop(0)です。性能差はあるのでしょうか？

質問

deque.popleft() と list.pop(0) は同じ結果を返すようです。両者にパフォーマンスの違いはあるのでしょうか、またその理由は？

解決方法は？

deque.popleft() は list.pop(0) よりも高速です。なぜなら deque は popleft() をおよそ O(1) で行うように最適化されており、一方 list.pop(0) には O(n) がかかるからです（参照）。 ディークオブジェクト ).

deque用の_collectionsmodule.cとlist用のlistobject.cのコメントとコードから、パフォーマンスの違いを説明する実装上の洞察が得られます。すなわち、dequeオブジェクトは2重にリンクされたリストで構成されており、両端での追加とポップを効果的に最適化します。一方、リストオブジェクトは単一にリンクされたリストですらなく、Cの配列（要素へのポインタの ( Python 2.7 listobject.h#l22 と Python 3.5 listobject.h#l23 このため、要素の高速ランダムアクセスには適していますが、最初の要素を削除した後、すべての要素を再配置するのにO(n)時間が必要です。

Python 2.7、3.5の場合、これらのソースコードのファイルのURLは以下の通りです。

1. https://hg.python.org/cpython/file/2.7/Modules/_collectionsmodule.c

2. https://hg.python.org/cpython/file/2.7/Objects/listobject.c

3. https://hg.python.org/cpython/file/3.5/Modules/_collectionsmodule.c

4. https://hg.python.org/cpython/file/3.5/Objects/listobject.c

timeit を使用すると、deque.popleft() と list.pop(0) の性能差は、deque と list が共に同じ 52 要素であれば約 4 倍、長さが 10**8 であれば 1000 倍以上になります。テスト結果は以下の通りです。

import string
from collections import deque

%timeit d = deque(string.letters); d.popleft()
1000000 loops, best of 3: 1.46 µs per loop

%timeit d = deque(string.letters)
1000000 loops, best of 3: 1.4 µs per loop

%timeit l = list(string.letters); l.pop(0)
1000000 loops, best of 3: 1.47 µs per loop

%timeit l = list(string.letters);
1000000 loops, best of 3: 1.22 µs per loop

d = deque(range(100000000))

%timeit d.popleft()
10000000 loops, best of 3: 90.5 ns per loop

l = range(100000000)

%timeit l.pop(0)
10 loops, best of 3: 93.4 ms per loop