Python: リストと辞書にin演算子を使った時の速さ
リストにinを使った場合
# listin.py n = 10**5 l = range(n) newlist = [] for i in range(n): if i*2 in l: newlist.append(i)
実行結果
$ time python listin.py real 2m32.296s user 2m31.573s sys 0m0.132s
辞書にinを使った場合
# dictin.py n = 10**5 l = dict(zip(range(n), range(n))) newlist = [] for i in range(n): if i*2 in l: newlist.append(i)
実行結果
$ time python dictin.py real 0m0.122s user 0m0.088s sys 0m0.032s
速さが違う理由(予想)
リストにin演算子を使うと、リストがその要素を持っているかを調べる。辞書にinを使う場合は、辞書がその要素をキーに持っているかを調べることになる。
リストの要素には数値、文字列以外のオブジェクトも存在する。そのためinをつかって要素を調べるためには要素をひとつずつ順に比較する必要がある。一方、辞書にinをつかう場合は辞書の要素を調べるのではなく、辞書のキーを調べる。キーは数値と文字列以外は存在しないためハッシュを使って探索できる。このような違いによってリストにin演算子を使うと辞書にin演算子を使った場合よりも遅くなる。
リストが数値や文字列しか持たない場合にin演算子を使うときは一度辞書に変換したほうが高速。