python：双端队列与列表性能比较

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

双端队列是堆栈和队列的概括（名称是 发音为“deck”，是“双端队列”的缩写）。德克斯 支持线程安全、内存高效的追加和弹出 双端队列的一侧具有大致相同的 O(1) 性能 任一方向。

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

我决定使用进行一些比较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

Could anyone explain me what I did wrong here

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

相反，您应该将您尝试测试的内容（弹出速度）与设置时间分开：

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

也就是说，双端队列和列表在性能方面的真正区别是：

• 双端队列的速度为 O(1)向左追加 () and 左移()而列表的性能为 O(n)插入（0，值） and pop(0).

• 列表追加性能时好时坏，因为它使用重新分配()在引擎盖下。因此，在简单代码中，它往往会出现过于乐观的计时（因为 realloc 不必移动数据），而在实际代码中，计时会非常缓慢（因为碎片迫使 realloc 移动所有数据）。相比之下，双端队列追加性能是一致的，因为它从不重新分配也从不移动数据。