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 に答える