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

Question

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

Answer 1

是的，如果您的列表或双端队列很长，这就很重要了。列表中的所有元素都连续放置在内存中，因此如果删除任何元素，所有后续元素都必须向左移动一个位置 - 因此，在列表开头删除或插入元素所需的时间与列表的长度。另一方面，双端队列专门用于允许在任一端快速插入或删除（通常通过在双端队列的开头允许 "empty" 内存位置，或者回绕使得双端队列占用的内存段的末尾可以包含实际被认为位于双端队列开头的元素。

比较这两个代码段的性能：

d = deque([0] * 1000000)
while d:
    d.popleft()
    if len(d) % 100 == 0:
        print(len(d))

lst = [0] * 1000000
while lst:
    lst.pop(0)
    if len(lst) % 100 == 0:
        print(len(lst))

Answer 2

Is there performance difference?

是的。 deque.popleft() 是 O(1) -- 常数时间操作。而 list.pop(0) 是 O(n) -- 线性时间操作：列表越大，花费的时间越长。

Why?

CPython 列表实现是基于数组的。 pop(0) 从列表中删除第一个项目，它需要向左移动 len(lst) - 1 个项目来填补空白。

deque() 实现使用双向链表。无论双端队列有多大，deque.popleft() 都需要一个常数（限制在上面）的操作数。

Answer 3

deque.popleft() 比 list.pop(0) 快，因为双端队列已经优化为在 O(1) 内执行 popleft()，而 list.pop(0 ) 需要 O(n)（参见 deque objects）。

_collectionsmodule.c 中用于双端队列和 listobject.c 中用于列表的注释和代码提供了实施见解以解释性能差异。即双端队列对象 "is composed of a doubly-linked list"，它有效地优化了两端的追加和弹出，而列表对象甚至不是单链表而是 C 数组（指向元素的指针（参见 Python 2.7 listobject.h#l22 and Python 3.5 listobject.h#l23），这使得它们适用于快速随机访问元素，但在移除第一个元素后需要 O(n) 时间来重新定位所有元素。

对于 Python 2.7 和 3.5，这些源代码文件的 URL 是：

使用 %timeit，当双端队列和列表都具有相同的 52 个元素并且增长到当它们的长度为 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

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

deque.popleft() and list.pop(0). Is there performance difference?

python

performance

list

deque

cpython