python - deque.popleft() vs list.pop(0)，性能分析

Question

根据 this question ，我检查了笔记本电脑的性能。

令人惊讶的是，我发现 pop(0)来自list比 popleft() 快来自deque结构:

python -m timeit 'l = range(10000)' 'l.pop(0)'

给出:

10000 loops, best of 3: 66 usec per loop

同时:

python -m timeit 'import collections' 'l = collections.deque(range(10000))' 'l.popleft()'

给出:

10000 loops, best of 3: 123 usec per loop

此外，我检查了 jupyter 的性能，发现了相同的结果:

%timeit l = range(10000); l.pop(0)

10000 loops, best of 3: 64.7 µs per loop

from collections import deque
%timeit l = deque(range(10000)); l.popleft()

10000 loops, best of 3: 122 µs per loop

这是什么原因？

Answer 1

问题是您的 timeit 调用也会对 deque/list creation 进行计时，而创建 deque 显然要慢得多，因为链接。

在命令行中，您可以使用 -s 选项将 setup 传递给 timeit，如下所示:

python -m timeit -s"import collections, time; l = collections.deque(range(10000000))" "l.popleft()"

此外，由于安装程序只运行一次，过一会儿你会得到一个弹出错误(空列表)，因为我没有更改默认的迭代次数，所以我创建了一个大的双端队列来弥补它，并得到

10000000 loops, best of 3: 0.0758 usec per loop

另一方面，list 速度较慢:

python -m timeit -s "l = list(range(10000000))" "l.pop(0)"
100 loops, best of 3: 9.72 msec per loop

我还在脚本中编写了工作台(更方便)、设置(以避免对设置计时)和 100000 大小列表上的 99999 次迭代:

import timeit

print(timeit.timeit(stmt='l.pop(0)',setup='l = list(range(100000))',number=99999))
print(timeit.timeit(setup='import collections; l = collections.deque(range(100000))', stmt='l.popleft()', number=99999))

毫不奇怪:deque 获胜:

2.442976927292288 for pop in list
0.007311641921253109 for pop in deque

请注意，列表的 l.pop() 在 0.011536903686244897 秒内运行，这在弹出最后一个元素时非常好，正如预期的那样。