python - Pythonの`in`キーワードは線形検索を実行しますか？

Question

Pythonは、指定された値がiterableusinginキーワードに存在するかどうかをどのようにチェックしますか。線形探索を実行しますか？好き：

def naive(iterable, val):
    for i in range(len(l)):
        if iterable[i]==val:
            return True
    return False

？または、それを行う別の方法があります。線形探索以外？

score 14 · Accepted Answer

Pythonのinオペレーターは__contains__、コンテナーでマジック関数を呼び出します。これは、コンテナごとに異なる方法で実装されます。

strings、lists、 sの場合tuple、これは線形検索（O(N)）ですが、Cで実装されているため、質問にある純粋なPythonよりも高速になる可能性があります。

setsとsの場合dict、これはハッシュテーブルルックアップであり、はるかに高速です（O(1)平均的な場合）。

他のコンテナは、異なるパフォーマンス特性を持ちます。標準ライブラリには何もないと思いますが、バランスの取れたツリーデータ構造はおそらくですO(log N)。

score 8 · Accepted Answer

inキーワードは、呼び出しているオブジェクトのクラスのメソッドの実装によって異なります__contains__。つまり、ハッシュ可能ではないもの（list、string）の場合は線形検索を実行しますが、ハッシュ可能なデータ構造（dict、set）の場合は一定時間で償却されます。

score 3 · Accepted Answer

はい、線形データ構造の場合は、線形検索です。例：リスト、文字列。セットの場合はO(1)操作であり、キーがdictにあるかどうかをチェックしている場合もO(1)です。

3 に答える 3