在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 = 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
也就是说，双端队列和列表在性能方面的真正区别是：
双端队列对于appendleft（）和popleft（）具有O（1）速度，而列表对于insert（0，value）和pop （0） ..
列表追加性能受到打击和错过，因为它在后台使用了realloc（）。结果，它倾向于在简单代码中具有过分乐观的时序（因为重新分配不必移动数据），而在实际代码中则确实具有较慢的时序（因为碎片迫使重新分配来移动所有数据）。相反，双端队列附加性能是一致的，因为它从不重新分配，也从不移动数据。
对于它的价值：
> 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
您可以看到，它真正发光的地方是appendleft与insert。
我建议您参考https://wiki.python.org/moin/TimeComplexity
Python列表和双端队列对大多数操作（推，弹出等）具有相似的复杂性