使用Python列表作为一个队列的效率(Efficiency of using a Python l

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

我知道，Python有collections.deque ，我试图找出是否要花我（有限）的时间来改写这个代码来使用它。假设我们执行数以百万计追加和持久性有机污染物，但从来没有超过几千项，将他的名单的使用是一个问题？

特别是，将底层阵列使用的Python列表执行会继续无限增长有几百万的斑点，即使只列出有一千个东西，或者将Python的最终做一个realloc ，释放一些内存？

Answer 1:

你会不会跑出来的使用内存list实现，但性能会很差。从该文档：

虽然list对象支持类似的操作，它们被用于快速固定长度的操作进行了优化，并招致为O（n），用于存储运动成本pop(0)和insert(0, v)操作，这些操作改变大小和底层数据表示的位置时，两个。

因此，使用deque会快很多。

Answer 2:

一些答案声称“10倍”的速度优势，为双端队列VS列表使用的-AS-FIFO时都有1000个条目，但是这是一个有点出价过高的：

$ 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是你的朋友-一个真正有用的和简单的微基准测试方法！有了它，你当然也可以平凡的探索备受较小的情况下的性能：

$ 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）双端队列的性能要求有充分的理由，而列表是在慢一倍左右1,000个项目，约10,000一个数量级。您还可以看到，即使在这种情况下，你只是在浪费每附加/流行对5微秒左右，决定浪费是如何显著（不过，如果这就是你要与容器做，双端队列没有缺点，所以你不妨切换即使5微秒或多或少不会让一个重要的区别）。

Answer 3:

从Beazley的Python的重要参考，第四版 ，第 194：

一些库模块提供了新的类型，在某些任务跑赢内置插件。例如，collections.deque类型提供类似的功能列表，但已经为高度在两端的物品的插入优化。列表，相反，附加在最后项目时，是唯一有效的。如果你在前面插入项目，所有其他元素的需要，以腾出空间来移动。要做到这一点所需的时间长的名单会越来越大。只是给你的不同的想法，这里是一个列表和双端队列的前面插入一个万件的定时测量：

还有如下的代码示例：

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