Python list pop（）比list[1:]慢得多

Question

我最近写了一个快速而肮脏的BFS实现，在有向图中找到菱形。 BFS循环如下所示：

while toVisit:
    y = toVisit.pop()
    if y in visited: return "Found diamond"
    visited.add(y)
    toVisit.extend(G[y])

（G是一个图表-从节点名到其邻居列表的字典）

接下来是有趣的部分： 我认为list.pop()可能太慢了，所以我运行了一个profiler来比较这个实现与deque.pop的速度，并得到了一些改进。然后我将它与y = toVisit[0]; toVisit = toVisit[1:]进行了比较，令我惊讶的是，最后一个实现实际上是最快的一个。

这有什么意义吗？ 是否有任何性能理由使用list.pop()而不是明显快得多的两行程序？

Answer 1

使用生成器执行

python -m timeit 'import itertools' 'l=iter(xrange(10000))' 'while next(l, None): l,a = itertools.tee(l)'

1000000 loops, best of 3: 0.986 usec per loop

Answer 2

你量错了。对于x64上的cPython 2.7，我得到了以下结果：

$ python -m timeit 'l = list(range(10000))' 'while l: l = l[1:]'
10 loops, best of 3: 365 msec per loop
$ python -m timeit 'l = list(range(10000))' 'while l: l.pop()'
1000 loops, best of 3: 1.82 msec per loop
$ python -m timeit 'import collections' \
         'l = collections.deque(list(range(10000)))' 'while l: l.pop()'
1000 loops, best of 3: 1.67 msec per loop