Python deque.popleft() 和 list.pop(0)。有性能差异吗？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/32543608/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
deque.popleft() and list.pop(0). Is there performance difference?
提问by Bin
deque.popleft()and list.pop(0)seem to return the same result. Is there any performance difference between them and why?
deque.popleft()并且list.pop(0)似乎返回相同的结果。它们之间是否有任何性能差异，为什么？
采纳答案by jfs
deque.popleft() is faster than list.pop(0), because the deque has been optimized to do popleft() approximately in O(1), while list.pop(0) takes O(n) (see deque objects).
deque.popleft() 比 list.pop(0) 快，因为 deque 已经优化为大约在 O(1) 中执行 popleft()，而 list.pop(0) 需要 O(n)（参见deque objects） .
Comments and code in _collectionsmodule.c for deque and listobject.c for list provide implementation insights to explain the performance differences. Namely that a deque object "is composed of a doubly-linked list", which effectively optimizes appends and pops at both ends, while list objects are not even singly-linked lists but C arrays (of pointers to elements (see Python 2.7 listobject.h#l22and Python 3.5 listobject.h#l23), which makes them good for fast random access of elements but requires O(n) time to reposition all elements after removal of the first.
_collectionsmodule.c 中用于 deque 的注释和代码和用于列表的 listobject.c 中的注释和代码提供了解释性能差异的实现见解。即 deque 对象“由双向链表组成”，它有效地优化了两端的追加和弹出，而列表对象甚至不是单链表而是 C 数组（指向元素的指针（参见Python 2.7 listobject.list）。 h#l22和Python 3.5 listobject.h#l23），这使得它们适合快速随机访问元素，但需要 O(n) 时间在删除第一个元素后重新定位所有元素。
For Python 2.7 and 3.5, the URLs of these source code files are:
对于 Python 2.7 和 3.5，这些源代码文件的 URL 是：
https://hg.python.org/cpython/file/2.7/Modules/_collectionsmodule.c
https://hg.python.org/cpython/file/3.5/Modules/_collectionsmodule.c
https://hg.python.org/cpython/file/2.7/Modules/_collectionsmodule.c
https://hg.python.org/cpython/file/3.5/Modules/_collectionsmodule.c
Using %timeit, the performance difference between deque.popleft() and list.pop(0) is about a factor of 4 when both the deque and the list have the same 52 elements and grows to over a factor of 1000 when their lengths are 10**8. Test results are given below.
使用 %timeit，deque.popleft() 和 list.pop(0) 之间的性能差异大约为 4 倍，当 deque 和列表具有相同的 52 个元素时，当它们的长度为 1000 时增长到 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
回答by Aasmund Eldhuset
Yes, and it's considerable if you have a long list or deque. All elements in a list are placed contiguously in memory, so if you remove any element, all subsequent elements must be shifted one position to the left - therefore, the time required to remove or insert an element at the start of a list is proportional to the length of the list. A deque, on the other hand, is specifically constructed to allow fast insertions or removal at eitherend (typically by allowing "empty" memory locations at the beginning of the deque, or to wrap around so that the end of the memory segment occupied by the deque can contain elements that are actually considered to be at the beginning of the deque).
是的，如果你有一个很长的列表或双端队列，这是相当可观的。列表中的所有元素都在内存中连续放置，因此如果删除任何元素，则所有后续元素都必须向左移动一个位置 - 因此，在列表开头删除或插入元素所需的时间与列表的长度。另一方面，双端队列被专门构造为允许在任一端进行快速插入或删除（通常通过在双端队列的开头允许“空”内存位置，或环绕以便内存段的末尾被占用双端队列可以包含实际上被认为是在双端队列开头的元素）。
Compare the performance of these two snippets:
比较这两个片段的性能：
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))
回答by jfs
Is there performance difference?
有性能差异吗？
Yes. deque.popleft()is O(1)-- a constant time operation. While list.pop(0)is O(n)-- linear time operation: the larger the list the longer it takes.
是的。deque.popleft()是O(1)——恒定时间操作。虽然list.pop(0)是O(n)-线性时间的操作：大名单花费的时间越长。
Why?
为什么？
CPython list implementation is array-based. pop(0)removes the first item from the list and it requires to shift left len(lst) - 1items to fill the gap.
CPython 列表实现是基于数组的。pop(0)从列表中删除第一个项目，它需要移动左边的len(lst) - 1项目来填补空白。
deque()implementation uses a doubly linked list. No matter how large the deque, deque.popleft()requires a constant (limited above) number of operations.
deque()实现使用双向链表。无论双端队列有多大，都deque.popleft()需要恒定（以上限制）的操作次数。
