0

我最近写了一个快速而肮脏的 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()而不是明显更快的两线？

4

2 回答 2

16

你测错了。在 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
于 2012-05-07T06:54:01.627 回答
0

使用生成器来提高性能

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

于 2014-01-19T11:49:49.340 回答