Pythonは、指定された値がiterableusingin
キーワードに存在するかどうかをどのようにチェックしますか。線形探索を実行しますか?好き :
def naive(iterable, val):
for i in range(len(l)):
if iterable[i]==val:
return True
return False
?または、それを行う別の方法があります。線形探索以外?
Pythonのin
オペレーターは__contains__
、コンテナーでマジック関数を呼び出します。これは、コンテナごとに異なる方法で実装されます。
str
ings、list
s、 sの場合tuple
、これは線形検索(O(N)
)ですが、Cで実装されているため、質問にある純粋なPythonよりも高速になる可能性があります。
set
sとsの場合dict
、これはハッシュテーブルルックアップであり、はるかに高速です(O(1)
平均的な場合)。
他のコンテナは、異なるパフォーマンス特性を持ちます。標準ライブラリには何もないと思いますが、バランスの取れたツリーデータ構造はおそらくですO(log N)
。
in
キーワードは、呼び出しているオブジェクトのクラスのメソッドの実装によって異なります__contains__
。つまり、ハッシュ可能ではないもの(list、string)の場合は線形検索を実行しますが、ハッシュ可能なデータ構造(dict、set)の場合は一定時間で償却されます。
はい、線形データ構造の場合は、線形検索です。例:リスト、文字列。セットの場合はO(1)
操作であり、キーがdictにあるかどうかをチェックしている場合もO(1)
です。