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

Question

最近，一个同事写了一个程序，他用Python的列表来当作队列。简单来说，他在需要添加东西的时候用.append(x)，而在需要移除东西的时候用.pop(0)。

我知道Python有一个叫做collections.deque的东西，我在考虑是否值得花时间把这段代码改成用它。假设我们要进行几百万次的添加和移除，但列表里从来不会超过几千个条目，这样用列表会有问题吗？

特别是，Python列表背后用的数组会不会无限增长，变成有几百万个位置，尽管列表里只有一千个东西？或者Python会不会最终做一个realloc，释放掉一些内存？

Answer 1

在Beazley的Python基础参考手册，第四版第194页中提到：

有些库模块提供的新类型在某些任务上比内置类型更高效。例如，collections.deque类型提供的功能和列表类似，但在两端插入项目时经过了高度优化。相比之下，列表在末尾添加项目时效率较高。如果你在前面插入项目，列表中的其他元素就需要移动，以腾出空间。随着列表变得越来越大，完成这个操作所需的时间也会增加。为了让你更好地理解这个差异，这里有一个关于在列表和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 2

有些回答说，当用1000个条目时，双端队列（deque）比用列表当作先进先出（FIFO）要快“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 是个好帮手——这是一个非常实用且简单的微基准测试方法！用它，你当然也可以轻松地测试更小规模的性能：

$ 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)性能是有根据的，而列表在大约1000个条目时慢了两倍，在大约10000个条目时慢了一个数量级。你还可以看到，即使在这种情况下，每次添加或删除一个条目，你也只会浪费大约5微秒，接下来你可以判断这个浪费有多重要（不过如果你只是用这个容器做这些操作，双端队列没有缺点，所以即使多或少5微秒也没什么大不了的，你完全可以考虑换成双端队列）。

Answer 3

使用 list 这种实现方式，你不会遇到内存不足的问题，但性能会比较差。根据官方文档的说法：

虽然 list 对象支持类似的操作，但它们是为了快速处理固定长度的操作而优化的。当你使用 pop(0) 或 insert(0, v) 这些操作时，会导致 O(n) 的内存移动成本，这意味着在改变数据的大小和位置时，会比较慢。

所以，使用 deque 会快很多。