python：deque vs列表性能比较 [英] 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，是双端队列）。 Deques
支持线程安全，高效率的追加和弹出，可以从deque的
一侧弹出，大致相同的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.

尽管列表对象支持类似的操作，但它们针对
快速固定长度操作进行了优化，并导致
pop（0）的O（n）内存移动成本，并插入（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

推荐答案

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

是的，你的时间主要是创建列表或deque的时间。

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 = 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

在表现方面，deques和list之间的真正差异是：

That said, the real differences between deques and list in terms of performance are:

• Deques具有O（1） appendleft（）和 popleft（），而列表对于插入（0，值）和 pop（0）具有O（n） em>。

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

列表附加性能受到打击，因为它使用了emloc（）。因此，它在简单的代码中往往会有过于乐观的时机（因为realloc不需要移动数据），并且真正减慢了实际代码中的时间（因为分片强制realloc来移动所有的数据）。相比之下，deque附加性能是一致的，因为它不会重新定位并且不会移动数据。

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：deque vs列表性能比较的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！