python - deque.popleft() 和 list.pop(0)。有性能差异吗？

Question

deque.popleft() 和 list.pop(0) 似乎返回相同的结果。它们之间有什么性能差异吗？为什么？

Answer 1

deque.popleft() 比 list.pop(0) 快，因为 deque 已被优化为大约在 O(1) 内执行 popleft()，而 list.pop(0) 需要 O(n)(请参阅deque objects ).

deque 的 _collectionsmodule.c 和 list 的 listobject.c 中的注释和代码提供了实现见解以解释性能差异。也就是说，双端队列对象“由双向链表组成”，它有效地优化了两端的追加和弹出，而列表对象甚至不是单链表而是 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，当双端队列和列表都具有相同的 52 个元素时，deque.popleft() 和 list.pop(0) 之间的性能差异大约是 4 倍，并且增长到超过 1000 倍时它们的长度是 10**8。测试结果如下。

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