使用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可能是在这里做的最好的事情 – 二阶问题可能会使实践中的一种方法更好，即使理论上它不是更好。
