python - Python fast contains メソッド

Question

Python で辞書を持っている場合、存在しないキーを検索する時間の複雑さはどのくらいですか?

d = {}
if key not in d:
   print "Key not found!"

inキーの配列全体で線形検索を行いますか?

特定の文字列のデータ構造を検索する O(1) 実装はありますか? メソッドとして効果的contains()。

Answer 1

最終的にオペレーターはメンバーシップ検索を実行するだけであり、追加のオーバーヘッドがないO(1)ため、ディクショナリに対して償却する必要があります。辞書の場合の演算子の時間の複雑さに関する詳細については、この回答をご覧ください。innotin

Answer 2

O(1) ディクショナリはハッシュ テーブルとして実装され、ハッシュ テーブル ルックアップを実行します。

Answer 3

辞書は通常、検索用に O(1) です。

ハッシュの定数を返すクラスを持つことは完全に受け入れられますが、これは辞書検索を線形に劣化させます。

例えば。

class dumbint(int):
    def __hash__(self):
        return 0

$ python -m timeit -s 'class dumbint(int):__hash__ = lambda x:0' -s 'd={dumbint(i):i for i in range(100)}' 'dumbint(-1) in d'
100000 loops, best of 3: 3.64 usec per loop
$ python -m timeit -s 'class dumbint(int):__hash__ = lambda x:0' -s 'd={dumbint(i):i for i in range(1000)}' 'dumbint(-1) in d'
10000 loops, best of 3: 31.7 usec per loop
$ python -m timeit -s 'class dumbint(int):__hash__ = lambda x:0' -s 'd={dumbint(i):i for i in range(10000)}' 'dumbint(-1) in d'
1000 loops, best of 3: 803 usec per loop

文字列には優れたハッシュ関数があるため、完全一致の O(1) ルックアップが得られます。キーの部分文字列を検索することは、はるかに難しい問題です。