setの話

checked が配列なので pos in checked が遅い。

勝手に採点 (Re: 自分ならこう書く - pythonでA*) - methaneのブログ

あー高速化のためにsetを使うってやったことなかったな。

計測

import timeit

a = range(100000)
b = set(a)

def test():
    return 100000 in a

def test2():
    return 100000 in b

res = timeit.timeit("test()", "from __main__ import test", number=1000)
print(res)
res = timeit.timeit("test2()", "from __main__ import test2", number=1000)
print(res)

結果

9.95783400536
0.000999927520752

set速えな。

生成（変換）コスト

こーいう処理になることはほとんどないのだけど、生成からinまで。

import timeit

def test():
    a = range(100000)
    return 100000 in a

def test2():
    a = range(100000)
    b = set(a)
    return 100000 in b

res = timeit.timeit("test()", "from __main__ import test", number=1000)
print(res)
res = timeit.timeit("test2()", "from __main__ import test2", number=1000)
print(res)

結果

16.2891459465
29.0829648972

inの部分はほぼ無視できるぐらいの速さなのだが、setを作るのはそれなりにコストが高いようだ。

setの注意

setになんでも突っ込んでいいのか？というとまあそうではなくて

set の要素は辞書のキーと同様に __hash__ と __eq__ の両方を定義していることが必要です。

http://www.python.jp/doc/release/lib/types-set.html

って制限もあるので注意。