Python列表pop()比列表[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()可能太慢了,所以我运行了一个分析器来比较这个实现的速度和deque.pop - 并得到了一点改进.然后我对它进行了比较y = toVisit[0]; toVisit = toVisit[1:],令我惊讶的是,最后一次实现实际上是最快的.

这有意义吗？是否有任何性能原因可以使用list.pop()而不是显然更快的双线程？

Answer 1

你测量错了.使用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