python:双端队列与列表性能比较 [英] python: deque vs list performance comparison

问题描述

在 python 文档中，我可以看到 deque 是一个特殊的集合，针对从左侧或右侧弹出/添加项目进行了高度优化.例如.文档说:

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:

Deques 是栈和队列的概括(名字是发音为deck"，是double-ended queue"的缩写).德克支持线程安全、内存高效的追加和弹出双端队列的一侧具有大致相同的 O(1) 性能任何一个方向.

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.

虽然列表对象支持类似的操作，但它们针对快速固定长度的操作并产生 O(n) 内存移动成本pop(0) 和 insert(0, v) 操作改变了大小和底层数据表示的位置.

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.

我决定使用 ipython 进行一些比较.谁能解释一下我在这里做错了什么:

I decided to make some comparisons using ipython. Could anyone explain me what I did wrong here:

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

推荐答案

谁能解释一下我在这里做错了什么

是的，您的时间由创建列表或双端队列的时间决定.相比之下，执行 pop 的时间微不足道.

Yes, your timing is dominated by the time to create the list or deque. The time to do the pop is 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:

• 对于 appendleft() 和 popleft()，Deques 的速度为 O(1)，而对于 insert(0)，列表的速度为 O(n), value) 和 pop(0).

• Deques have O(1) speed for appendleft() and popleft() while lists have O(n) performance for insert(0, value) and pop(0).

List append 的性能很受打击，因为它在幕后使用了 realloc().因此，它在简单代码中往往具有过于乐观的时序(因为 realloc 不必移动数据)，而在实际代码中的时序确实很慢(因为碎片迫使 realloc 移动所有数据).相比之下，deque append 性能是一致的，因为它从不重新分配也从不移动数据.

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.

这篇关于python:双端队列与列表性能比较的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！