3

100000 を超える値のリストがあり、これらの値を反復処理して、それぞれが (同じサイズの) ランダム値の別のリストに含まれているかどうかを確認しています。

を使用してこれを行っていif item[x] in randomListます。これはどのくらい効率的ですか？Python はコンテナごとに何らかのハッシュ処理を行っていますか、それとも探している要素を見つけるために他のコンテナを直接検索していますか?

また、この検索を直線的に行う場合、randomList の辞書を作成し、それを使用してルックアップを行いますか?

4

4 に答える 4

8

in適用されるオブジェクトの魔法の方法によって実装される__contains__ため、効率はそれに依存します。たとえばset、dictとfrozensetはハッシュ ベースのルックアップにlistなりますが、線形検索が必要になります。ただし、xrange(またはrangePython 3.x では)__contains__線形検索を必要としないメソッドがありますが、代わりに開始/停止/ステップ情報を使用して真の値を決定できます。(例:7 in xrange(4, 1000000)直線的には行われません)。

カスタムクラスは自由に実装でき__contains__ますが、適切と思われますが、「明らかでない」場合は、ドキュメントで実装方法に関する情報を提供するのが理想的です。

于 2013-06-20T17:50:46.810 に答える
2

O(1) ルックアップにハッシュを使用できるように、リストをセットに事前変換する必要があります。

http://wiki.python.org/moin/TimeComplexityを参照

(通常、「古典的な」リスト内のすべての要素を検索して、その中に何かがあるかどうかを確認する必要があります (ただし、データ構造がすべての要素のセットを保持している場合を除きますが、それは膨大な時間とスペースの複雑さを追加し、プログラマーは自分で実装できます))。

于 2013-06-20T17:43:47.223 に答える
0

ninjagecko はすでにリスト (およびタプル FWIW) の特定のケースに回答していますが、一般的な回答は次のとおりです。組み込み型の場合、高速検索のためにセットまたはディクテーションが必要です。それ以外の場合は、コンテナーのドキュメントまたは実装を確認することをお勧めします。

于 2013-06-20T17:55:35.820 に答える
0

次のように、2 つのリストが並べ替えられている場合は、セットを使用せずにこれを行うことができます。

def gen(P1, P2):
    i, j = 0, 0
    I, J = len(P1), len(P2)
    while i != I and j != J:
        if P1[i] == P2[j]:
            yield P1[i]
            i, j = i + 1, j + 1
        else:
            if P1[i] < P2[j]:
                i += 1
            else:
                j += 1

これは、P1 と P2 の交点を返します。

>>> P1 = [1, 2, 3, 5, 90]
>>> P2 = [2, 3, 5, 30, 48]
>>> list(gen(P1, P2))
[2, 3, 5]

アルゴリズムはここで説明されています。

于 2013-06-20T17:59:06.060 に答える