python：双端队列与列表性能比较
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/23487307/
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
python: deque vs list performance comparison
提问by Oleg Tarasenko
In python docs I can see that deque is a special collection highly optimized for poping/adding items from left or right sides. E.g. documentation says:
在 python 文档中，我可以看到 deque 是一个高度优化的特殊集合，用于从左侧或右侧弹出/添加项目。例如文档说：
Deques are a generalization of stacks and queues (the name is pronounced “deck” and is short for “double-ended queue”). Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.
Though list objects support similar operations, they are optimized for fast fixed-length operations and incur O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation.
双端队列是栈和队列的泛化（名称发音为“deck”，是“双端队列”的缩写）。双端队列支持线程安全、内存高效的追加和从双端队列的任一侧弹出，在任一方向上的 O(1) 性能大致相同。
尽管列表对象支持类似的操作，但它们针对快速固定长度操作进行了优化，并且会为 pop(0) 和 insert(0, v) 操作带来 O(n) 内存移动成本，这会改变底层数据表示的大小和位置.
I decided to make some comparisons using ipython. Could anyone explain me what I did wrong here:
我决定使用ipython进行一些比较。谁能解释一下我在这里做错了什么：
In [31]: %timeit range(1, 10000).pop(0)
10000 loops, best of 3: 114 us per loop
In [32]: %timeit deque(xrange(1, 10000)).pop()
10000 loops, best of 3: 181 us per loop
In [33]: %timeit deque(range(1, 10000)).pop()
1000 loops, best of 3: 243 us per loop
回答by sberry
For what it is worth:
对于它的价值：
> python -mtimeit -s 'import collections' -s 'c = collections.deque(xrange(1, 100000000))' 'c.pop()'
10000000 loops, best of 3: 0.11 usec per loop
> python -mtimeit -s 'c = range(1, 100000000)' 'c.pop()'
10000000 loops, best of 3: 0.174 usec per loop
> python -mtimeit -s 'import collections' -s 'c = collections.deque()' 'c.appendleft(1)'
10000000 loops, best of 3: 0.116 usec per loop
> python -mtimeit -s 'c = []' 'c.insert(0, 1)'
100000 loops, best of 3: 36.4 usec per loop
As you can see, where it really shines is in appendleftvs insert.
正如你所看到的，它真正闪耀的地方是appendleftvs insert。
回答by Raymond Hettinger
Could anyone explain me what I did wrong here
Could anyone explain me what I did wrong here
Yes, your timing is dominated by the time to create the list or deque. The time to do the popis insignificant in comparison.
是的，您的时间由创建列表或双端队列的时间决定。相比之下，做流行音乐的时间微不足道。
Instead you should isolate the thing you're trying to test (the pop speed) from the setup time:
相反，您应该将您尝试测试的内容（弹出速度）与设置时间隔离开来：
In [1]: from collections import deque
In [2]: s = list(range(1000))
In [3]: d = deque(s)
In [4]: s_append, s_pop = s.append, s.pop
In [5]: d_append, d_pop = d.append, d.pop
In [6]: %timeit s_pop(); s_append(None)
10000000 loops, best of 3: 115 ns per loop
In [7]: %timeit d_pop(); d_append(None)
10000000 loops, best of 3: 70.5 ns per loop
That said, the real differences between deques and list in terms of performance are:
也就是说，双端队列和列表在性能方面的真正区别是：
Deques have O(1) speed for appendleft()and popleft()while lists have O(n) performance for insert(0, value)and pop(0).
List append performance is hit and miss because it uses realloc()under the hood. As a result, it tends to have over-optimistic timings in simple code (because the realloc doesn't have to move data) and really slow timings in real code (because fragmentation forces realloc to move all the data). In contrast, deque append performance is consistent because it never reallocs and never moves data.
双端队列的appendleft()和popleft() 速度为 O(1)，而列表的insert(0, value)和pop(0) 的速度为O(n )。
列表追加的性能时好时坏，因为它在底层使用了realloc()。因此，它在简单代码中往往具有过于乐观的时序（因为 realloc 不必移动数据），而在实际代码中的时序确实很慢（因为碎片迫使 realloc 移动所有数据）。相比之下，deque append 性能是一致的，因为它从不重新分配也从不移动数据。
回答by Krishan Chopra
I would recommend you to refer https://wiki.python.org/moin/TimeComplexity
我建议您参考 https://wiki.python.org/moin/TimeComplexity
Python lists and deque have simlilar complexities for most operations(push,pop etc.)
Python 列表和双端队列对于大多数操作（推送、弹出等）具有相似的复杂性
回答by ccchoy
I found my way to this question and thought I'd offer up an example with a little context.
A classic use-case for using a Deque might be rotating/shifting elements in a collection because (as others have mentioned), you get very good (O(1)) complexity for push/pop operations on both ends because these operations are just moving references around as opposed to a list which has to physically move objects around in memory.
我找到了解决这个问题的方法，并认为我会提供一个带有一点上下文的示例。
使用 Deque 的一个经典用例可能是旋转/移动集合中的元素，因为（正如其他人所提到的），对于两端的 push/pop 操作，您会获得非常好的 (O(1)) 复杂度，因为这些操作只是移动引用而不是必须在内存中物理移动对象的列表。
So here are 2 verysimilar-looking implementations of a rotate-left function:
所以这里有两个非常相似的左旋转函数的实现：
def rotate_with_list(items, n):
l = list(items)
for _ in range(n):
l.append(l.pop(0))
return l
from collections import deque
def rotate_with_deque(items, n):
d = deque(items)
for _ in range(n):
d.append(d.popleft())
return d
Note: This is such a common use of a deque that the deque has a built-in
rotatemethod, but I'm doing it manually here for the sake of visual comparison.
注意：这是 deque 的一种常见用法，deque 有一个内置
rotate方法，但为了视觉比较，我在这里手动执行。
Now let's %timeit.
现在让我们%timeit。
In [1]: def rotate_with_list(items, n):
...: l = list(items)
...: for _ in range(n):
...: l.append(l.pop(0))
...: return l
...:
...: from collections import deque
...: def rotate_with_deque(items, n):
...: d = deque(items)
...: for _ in range(n):
...: d.append(d.popleft())
...: return d
...:
In [2]: items = range(100000)
In [3]: %timeit rotate_with_list(items, 800)
100 loops, best of 3: 17.8 ms per loop
In [4]: %timeit rotate_with_deque(items, 800)
The slowest run took 5.89 times longer than the fastest. This could mean that an intermediate result is being cached.
1000 loops, best of 3: 527 μs per loop
In [5]: %timeit rotate_with_list(items, 8000)
10 loops, best of 3: 174 ms per loop
In [6]: %timeit rotate_with_deque(items, 8000)
The slowest run took 8.99 times longer than the fastest. This could mean that an intermediate result is being cached.
1000 loops, best of 3: 1.1 ms per loop
In [7]: more_items = range(10000000)
In [8]: %timeit rotate_with_list(more_items, 800)
1 loop, best of 3: 4.59 s per loop
In [9]: %timeit rotate_with_deque(more_items, 800)
10 loops, best of 3: 109 ms per loop
Pretty interesting how both data structures expose an eerily similar interface but have drastically different performance :)
非常有趣的是，这两种数据结构如何公开一个非常相似的界面，但性能却截然不同:)
