6

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

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

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

4

3 に答える 3

14

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

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

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

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

于 2013-03-11T04:03:26.710 に答える
8

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

于 2013-03-11T03:59:59.957 に答える
3

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

于 2013-03-11T03:59:53.877 に答える