☰

Pythonでリストがアイテムを共有しているかどうかをテストする 質問する

tag-icon • tag-icon list python intersection
Pythonでリストがアイテムを共有しているかどうかをテストする 質問する

確認したいどれでもあるリストの項目のうち、別のリストに存在しているものを検索します。以下のコードで簡単に実行できますが、これを行うためのライブラリ関数があるのではないかと思います。そうでない場合、同じ結果を達成するためのより Python 的な方法はありますか。

In [78]: a = [1, 2, 3, 4, 5]

In [79]: b = [8, 7, 6]

In [80]: c = [8, 7, 6, 5]

In [81]: def lists_overlap(a, b):
   ....:     for i in a:
   ....:         if i in b:
   ....:             return True
   ....:     return False
   ....: 

In [82]: lists_overlap(a, b)
Out[82]: False

In [83]: lists_overlap(a, c)
Out[83]: True

In [84]: def lists_overlap2(a, b):
   ....:     return len(set(a).intersection(set(b))) > 0
   ....:

ベストアンサー1

短い答え: を使用するとnot set(a).isdisjoint(b)、一般的に最も高速になります。

a2 つのリストに共通する項目があるかどうかをテストする一般的な方法は 4 つありますb。最初のオプションは、次のように両方をセットに変換して、それらの交差をチェックすることです。

bool(set(a) & set(b))

なぜならPythonではハッシュテーブルを使ってセットが保存されるので、それを検索するのはO(1)（見るここPythonの演算子の複雑さの詳細については、こちらをご覧ください。理論的には、リストとオブジェクトの平均O(n+m)では、これは です。しかし、nmab

  1. まずリストからセットを作成する必要があり、これにはかなりの時間がかかる。
  2. データ間でハッシュ衝突が散発的に発生することを前提としています。

2 番目の方法は、次のようにリストの反復処理を実行するジェネレータ式を使用することです。

any(i in a for i in b)

これにより、インプレース検索が可能になり、中間変数に新しいメモリが割り当てられなくなります。また、最初の検索で終了します。しかし、inオペレーターは常にO(n)リストに載っています（見るここ）。

提案されているもう 1 つのオプションは、リストの 1 つを反復処理し、セット内のもう 1 つを変換して、このセットのメンバーシップをテストするハイブリッドです。次のようになります。

a = set(a); any(i in a for i in b)

4番目のアプローチは、isdisjoint()（凍結）セット法を利用することです（ここ）、 例えば：

not set(a).isdisjoint(b)

検索する要素が配列の先頭近くにある場合 (ソートされている場合など)、集合交差メソッドでは中間変数に新しいメモリを割り当てる必要があるため、ジェネレータ式が優先されます。

from timeit import timeit
>>> timeit('bool(set(a) & set(b))', setup="a=list(range(1000));b=list(range(1000))", number=100000)
26.077727576019242
>>> timeit('any(i in a for i in b)', setup="a=list(range(1000));b=list(range(1000))", number=100000)
0.16220548999262974

以下は、リスト サイズの関数としてこの例の実行時間を示したグラフです。

最初に共有した場合の要素共有テスト実行時間

両方の軸が対数であることに注意してください。これは、ジェネレータ式の最良のケースを表しています。ご覧のとおり、このisdisjoint()方法はリストのサイズが非常に小さい場合に適しており、ジェネレータ式はリストのサイズが大きい場合に適しています。

一方、ハイブリッド式とジェネレータ式では検索が先頭から始まるため、共有要素が配列の末尾に体系的にある場合 (または両方のリストが値を共有していない場合)、分離アプローチと集合積アプローチは、ジェネレータ式とハイブリッド アプローチよりもはるかに高速になります。

>>> timeit('any(i in a for i in b)', setup="a=list(range(1000));b=[x+998 for x in range(999,0,-1)]", number=1000))
13.739536046981812
>>> timeit('bool(set(a) & set(b))', setup="a=list(range(1000));b=[x+998 for x in range(999,0,-1)]", number=1000))
0.08102107048034668

最後に共有する場合の要素共有テスト実行時間

興味深いことに、ジェネレータ式はリストのサイズが大きいほど遅くなります。これは、前の図の 100000 回ではなく、1000 回の繰り返しの場合のみです。この設定は、要素が共有されていない場合にも適切に近似され、分離アプローチと集合積アプローチに最適なケースです。

以下は、乱数を使用した 2 つの分析です (いずれかの手法を優先するように設定を操作するのではなく)。

共有される可能性が高いランダムに生成されたデータの要素共有テスト実行時間 共有される可能性が高いランダムに生成されたデータの要素共有テスト実行時間

共有される可能性が高い: 要素は からランダムに取得されます[1, 2*len(a)]。共有される可能性が低い: 要素は からランダムに取得されます[1, 1000*len(a)]。

これまでの分析では、両方のリストが同じサイズであると想定していました。2 つのリストのサイズが異なる場合、たとえばリストaがはるかに小さい場合は、isdisjoint()常に高速になります。

最初に共有された場合の2つの異なるサイズのリストでの要素共有テストの実行時間 最後に共有された場合の 2 つの異なるサイズのリストでの要素共有テスト実行時間

リストが小さいことを確認してくださいa。小さいとパフォーマンスが低下します。この実験では、aリストのサイズは一定に設定されました5。

要約すれば：

  • リストが非常に小さい場合 (要素数が 10 未満)、not set(a).isdisjoint(b)常に最速になります。
  • リスト内の要素がソートされているか、または利用できる規則的な構造を持っている場合、ジェネレータ式はany(i in a for i in b)大きなリスト サイズで最も高速になります。
  • との集合積をテストしますnot set(a).isdisjoint(b)。これは常に よりも高速ですbool(set(a) & set(b))。
  • 「リストを反復処理し、セットでテストする」というハイブリッド方法は、a = set(a); any(i in a for i in b)通常、他の方法よりも遅くなります。
  • ジェネレータ式とハイブリッドは、要素を共有しないリストの場合、他の 2 つのアプローチよりもはるかに遅くなります。

ほとんどの場合、isdisjoint()要素が共有されていない場合には非常に非効率であり、ジェネレータ式の実行に非常に長い時間がかかるため、メソッドを使用するのが最善の方法です。

おすすめ記事