deque.popleft()和list.pop(0).有性能差异吗? [英] deque.popleft() and list.pop(0). Is there performance difference?
问题描述
deque.popleft()和list.pop(0)似乎返回相同的结果.它们之间有什么性能差异，为什么?
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)更快，因为该双端队列已被优化为可以在O(1)中执行popleft()，而list.pop(0)为O(n)(请参见双端对象).
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).
_queue的_collectionsmodule.c和list的listobject.c中的注释和代码提供了实现见解，以解释性能差异.即，双端队列对象由双向链接列表组成"，可以有效地优化两端的追加和弹出，而列表对象甚至不是单链接列表，而是C数组(指向元素的指针(请参见 Python 2.7 listobject.h#l22 和
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#l22 and 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.
对于Python 2.7和3.5，这些源代码文件的URL为:
For Python 2.7 and 3.5, the URLs of these source code files are:
https://hg.python.org/cpython /file/2.7/Objects/listobject.c
https://hg.python.org/cpython /file/3.5/Modules/_collectionsmodule.c
https://hg.python.org/cpython /file/3.5/Objects/listobject.c
使用％timeit，当双端队列和列表具有相同的52个元素时，deque.popleft()和list.pop(0)之间的性能差异约为4倍，而当deque.popleft(list)具有相同的52个元素时，性能差异超过1000倍它们的长度是10 ** 8.测试结果如下.
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.
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).有性能差异吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
