在python文档中,我可以看到deque是一个特别的集合,高度优化从左侧或右侧弹出/添加项目.例如文件说:
Deques是堆栈和队列的概括(名称发音为"deck",是"双端队列"的缩写).Deques支持线程安全,内存有效的附加和从双端队列的弹出,在任一方向上具有大致相同的O(1)性能.
尽管列表对象支持类似的操作,但它们针对快速固定长度操作进行了优化,并导致pop(0)和insert(0,v)操作的O(n)内存移动成本,这些操作改变了底层数据表示的大小和位置.
我决定使用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
Raymond Hett.. 74
Could anyone explain me what I did wrong here
是的,您的时间由创建列表或双端队列的时间决定.相比之下,做流行音乐的时间微不足道.
相反,你应该从设置时间中隔离你想要测试的东西(弹出速度):
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在性能方面的真正区别是:
Deques对appendleft()和popleft()的速度为O(1),而list对于insert(0,value)和pop(0)具有O(n)性能.
列表附加性能是命中和未命中,因为它在引擎盖下使用realloc().因此,它往往在简单代码中具有过度乐观的时序(因为realloc不必移动数据)并且实际代码中的时间确实很慢(因为碎片强制重新分配以移动所有数据).相比之下,deque追加性能是一致的,因为它永远不会重新分配并且永远不会移动数据.
是的,它使用链表逻辑.更具体地说,它使用固定长度块的双向链表. (7认同)
对列表使用`realloc()`只是一种优化.每次调整大小时,列表都会被过度分配,以保证O(1)摊销附加性能,即使必须在每次调整大小时复制数据. (2认同)
sberry.. 20
对于它的价值:
> 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
VS insert
.