使用Python列表作为队列的效率

最近一位同事写了一个程序,用Python列表作为队列。 换句话说,当需要插入项目时使用了.append(x) ,而在需要删除项目时使用了.pop(0)

我知道Python有collections.deque ,我试图找出是否花费我的(有限的)时间来重写这段代码来使用它。 假设我们执行数以百万计的追加和popup,但从来没有超过几千个条目,他的列表使用会成为一个问题?

特别是,Python列表实现所使用的底层数组是否会继续无限增长,即使列表只有一千个东西,或者Python最终是否会重新realloc并释放一些内存?

使用list实现不会耗尽内存,但性能会很差。 从文档 :

虽然list对象支持类似的操作,但是它们针对快速固定长度操作进行了优化,并且对pop(0)insert(0, v)操作产生O(n)存储器移动成本,这些操作改变了底层数据表示的大小和位置。

所以使用deque将会快得多。

一些答案声称,当双方都有1000个条目时,双向链表和列表使用的速度优势是“10倍”的速度优势,但这有点过高:

 $ python -mtimeit -s'q=range(1000)' 'q.append(23); q.pop(0)' 1000000 loops, best of 3: 1.24 usec per loop $ python -mtimeit -s'import collections; q=collections.deque(range(1000))' 'q.append(23); q.popleft()' 1000000 loops, best of 3: 0.573 usec per loop 

python -mtimeit是你的朋友 – 一个非常有用和简单的微观基准testing方法! 有了它,你当然也可以在更小的情况下轻松地探索性能:

 $ python -mtimeit -s'q=range(100)' 'q.append(23); q.pop(0)' 1000000 loops, best of 3: 0.972 usec per loop $ python -mtimeit -s'import collections; q=collections.deque(range(100))' 'q.append(23); q.popleft()' 1000000 loops, best of 3: 0.576 usec per loop 

(12个而不是100个项目不是很不一样),以及更大的:

 $ python -mtimeit -s'q=range(10000)' 'q.append(23); q.pop(0)' 100000 loops, best of 3: 5.81 usec per loop $ python -mtimeit -s'import collections; q=collections.deque(range(10000))' 'q.append(23); q.popleft()' 1000000 loops, best of 3: 0.574 usec per loop 

你可以看到O(1)对Deque性能的要求是有充分依据的,而一个列表的速度却是一千个左右的两倍,大约是一万个左右。 你也可以看到,即使在这种情况下,你每浪子只浪费5微秒左右的时间,并决定这个浪费是多么的重要(尽pipe如此,你用这个容器做的事情,deque没有缺点,所以你不妨多切换一下5即可)。

从Beazley的Python Essential Reference,第四版 ,p。 194:

某些库模块提供了在某些任务中胜过内置的新types。 例如,collections.dequetypes提供了类似于列表的function,但是为了在两端插入项目而进行了高度优化。 相反,列表只有在最后追加项目时才有效。 如果您在前面插入物品,则需要移动所有其他元素才能腾出空间。 随着名单变得越来越大,这样做所需的时间也在增加。 为了给你一个差异的想法,下面是一个在列表和前端插入一百万个项目的时间测量:

接下来是这个代码示例:

 >>> from timeit import timeit >>> timeit('s.appendleft(37)', 'import collections; s = collections.deque()', number=1000000) 0.13162776274638258 >>> timeit('s.insert(0,37)', 's = []', number=1000000) 932.07849908298408 

时间来自我的机器。


2012-07-01更新

 >>> from timeit import timeit >>> n = 1024 * 1024 >>> while n > 1: ... print '-' * 30, n ... timeit('s.appendleft(37)', 'import collections; s = collections.deque()', number=n) ... timeit('s.insert(0,37)', 's = []', number=n) ... n >>= 1 ... ------------------------------ 1048576 0.1239769458770752 799.2552740573883 ------------------------------ 524288 0.06924104690551758 148.9747350215912 ------------------------------ 262144 0.029170989990234375 35.077512979507446 ------------------------------ 131072 0.013737916946411133 9.134140014648438 ------------------------------ 65536 0.006711006164550781 1.8818109035491943 ------------------------------ 32768 0.00327301025390625 0.48307204246520996 ------------------------------ 16384 0.0016388893127441406 0.11021995544433594 ------------------------------ 8192 0.0008249282836914062 0.028419017791748047 ------------------------------ 4096 0.00044918060302734375 0.00740504264831543 ------------------------------ 2048 0.00021195411682128906 0.0021741390228271484 ------------------------------ 1024 0.00011205673217773438 0.0006101131439208984 ------------------------------ 512 6.198883056640625e-05 0.00021386146545410156 ------------------------------ 256 2.9087066650390625e-05 8.797645568847656e-05 ------------------------------ 128 1.5974044799804688e-05 3.600120544433594e-05 ------------------------------ 64 8.821487426757812e-06 1.9073486328125e-05 ------------------------------ 32 5.0067901611328125e-06 1.0013580322265625e-05 ------------------------------ 16 3.0994415283203125e-06 5.9604644775390625e-06 ------------------------------ 8 3.0994415283203125e-06 5.0067901611328125e-06 ------------------------------ 4 3.0994415283203125e-06 4.0531158447265625e-06 ------------------------------ 2 2.1457672119140625e-06 2.86102294921875e-06 

每个.pop(0)需要N个步骤,因为该列表必须重新组织。 所需的记忆不会无止境地增长,只有持有物品所需的记忆力才会大。

我build议使用deque来获得O(1)追加和从前面popup。

这听起来像是一些经验性的testing可能是在这里做的最好的事情 – 二阶问题可能会使实践中的一种方法更好,即使理论上它不是更好。