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

Question

一位同事最近编写了一个程序,其中他使用Python列表作为队列.换句话说,他.append(x)在需要插入物品时和.pop(0)需要移除物品时使用.

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

特别是,Python列表实现使用的底层数组是否会无限增长,有数百万个点,即使列表只有一千个,或者Python最终会做一个realloc并释放一些内存？

Answer 1

一些答案声称,当两者都有1000个条目时,deque vs list-used-as-FIFO的速度优势为"10x",但这有点过分了:

$ 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项btw来说差别不大),而且在更大的那些:

$ 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

你可以看出,deque的O(1)性能声称是有根据的,而列表的速度是1,000个项目的两倍,一个数量级大约10,000.您还可以看到,即使在这种情况下,您每次附加/弹出对只会浪费5微秒左右,并决定浪费的重要程度(尽管如果您正在使用该容器做什么,deque没有任何缺点,所以你即使5或多或少使用不会产生重大影响,也可以切换.

Answer 2

使用该list实现不会耗尽内存,但性能会很差.来自文档:

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

所以使用a deque会快得多.

Answer 3

来自Beazley的Python Essential Reference,第四版,p.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

Answer 4

每个都.pop(0)需要 N 步，因为列表必须重新组织。所需的内存不会无休止地增长，只会与所持有的物品所需的一样大。

我建议使用deque从前面获取 O(1) 附加和弹出。