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

Question

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

我知道Python有^{}，我正试图弄清楚是否要花费我（有限的）时间重写这段代码来使用它。假设我们执行数百万个appends和pop，但从来没有超过几千个条目，那么他的列表使用会成为一个问题吗？

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

Answer 1

一些答案声称，当deque vs list都有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是您的朋友——一个非常有用和简单的微基准测试方法！当然，使用它，您还可以在更小的情况下轻松地探索性能：

$ 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）性能声明是有根据的，而一个列表在1000个项目上的速度是原来的两倍多，在10000个数量级左右。您还可以看到，即使在这种情况下，每个append/pop对您只浪费了5微秒左右，并决定这种浪费有多大（尽管如果这就是您对该容器所做的一切，deque没有缺点，所以您最好切换，即使5个usec或多或少不会产生重要影响）。

Answer 2

摘自比兹利的Python Essential Reference, Fourth Edition，第194页：

Some library modules provide new types that outperform the built-ins at certain tasks. For instance, collections.deque type provides similar functionality to a list but has been highly optimized for the insertion of items at both ends. A list, in contrast, is only efficient when appending items at the end. If you insert items at the front, all of the other elements need to be shifted in order to make room. The time required to do this grows as the list gets larger and larger. Just to give you an idea of the difference, here is a timing measurement of inserting one million items at the front of a list and a 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 3

使用list实现不会耗尽内存，但性能会很差。来自the docs：

Though list objects support similar operations, they are optimized for fast fixed-length operations and incur O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation.

所以使用deque会快得多。