164

あるリストの項目が別のリストにあるかどうかを確認したい。以下のコードで簡単にできますが、これを行うためのライブラリ関数があるのではないかと思います。そうでない場合は、同じ結果を達成するためのより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
   ....:
4

9 に答える 9

405

簡単な答え：使用してくださいnot set(a).isdisjoint(b)、それは一般的に最速です。

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

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

セットはPythonのハッシュテーブルを使用して保存されるO(1)ため、それらを検索することは可能です（Pythonの演算子の複雑さの詳細については、ここを参照してください）。理論的には、これはリストとのオブジェクトのO(n+m)平均です。ただし、1）最初にリストからセットを作成する必要があります。これには無視できない時間がかかる可能性があります。2）ハッシュの衝突がデータ間でまばらであると想定しています。nmab

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

any(i in a for i in b)

これにより、インプレース検索が可能になるため、中間変数に新しいメモリが割り当てられることはありません。それはまた、最初の発見で保釈されます。ただし、in演​​算子は常にO(n)リストにあります（ここを参照）。

別の提案されたオプションは、次のように、リストの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()要素が共有されていない場合は非常に非効率的であるため、ジェネレータ式の実行にはるかに長い時間がかかるため、このメソッドを使用するのが最善のアプローチです。

于 2013-07-18T23:06:05.867 に答える
27 
def lists_overlap3(a, b):
    return bool(set(a) & set(b))

注：上記は、答えとしてブール値が必要であることを前提としています。ifステートメントで使用する式だけが必要な場合は、if set(a) & set(b):

于 2010-07-03T02:21:39.280 に答える
11 
def lists_overlap(a, b):
  sb = set(b)
  return any(el in sb for el in a)

これは漸近的に最適であり（最悪の場合O（n + m））、any短絡のために交差アプローチよりも優れている可能性があります。

例えば：

lists_overlap([3,4,5], [1,2,3])

に到達するとすぐにTrueを返します3 in sb

編集：別のバリエーション（Dave Kirbyのおかげで）：

def lists_overlap(a, b):
  sb = set(b)
  return any(itertools.imap(sb.__contains__, a))

imapこれは、ジェネレーターの理解ではなく、Cで実装されているイテレーターに依存しています。sb.__contains__マッピング機能としても使用します。これによってパフォーマンスがどの程度異なるかはわかりません。それでも短絡します。

于 2010-07-03T02:40:59.747 に答える
5

anyリスト内包表記で使用することもできます。

any([item in a for item in b])
于 2010-07-03T02:23:42.367 に答える
3

Python 2.6以降では、次のことができます。

return not frozenset(a).isdisjoint(frozenset(b))
于 2012-11-13T10:49:47.933 に答える
2

任意の組み込み関数/waジェネレータ式を使用できます。

def list_overlap(a,b): 
     return any(i for i in a if i in b)

JohnとLieが指摘したように、2つのリストで共有されるすべてのiに対してbool（i）== Falseの場合、これは誤った結果をもたらします。そのはず：

return any(i in b for i in a)
于 2010-07-03T02:28:26.743 に答える
1

この質問はかなり古いものですが、人々がセットとリストについて議論している間、誰もそれらを一緒に使用することを考えていなかったことに気づきました。Soravuxの例に従って、

リストの最悪の場合：

>>> timeit('bool(set(a) & set(b))',  setup="a=list(range(10000)); b=[x+9999 for x in range(10000)]", number=100000)
100.91506409645081
>>> timeit('any(i in a for i in b)', setup="a=list(range(10000)); b=[x+9999 for x in range(10000)]", number=100000)
19.746716022491455
>>> timeit('any(i in a for i in b)', setup="a= set(range(10000)); b=[x+9999 for x in range(10000)]", number=100000)
0.092626094818115234

そしてリストの最良のケース：

>>> timeit('bool(set(a) & set(b))',  setup="a=list(range(10000)); b=list(range(10000))", number=100000)
154.69790101051331
>>> timeit('any(i in a for i in b)', setup="a=list(range(10000)); b=list(range(10000))", number=100000)
0.082653045654296875
>>> timeit('any(i in a for i in b)', setup="a= set(range(10000)); b=list(range(10000))", number=100000)
0.08434605598449707

したがって、2つのリストを反復処理するよりもさらに高速なのは、リストを反復処理してセット内にあるかどうかを確認することです。これは、数値がセット内にあるかどうかのチェックには一定の時間がかかり、リストを反復処理することによるチェックには、リスト。

したがって、私の結論は、リストを反復処理し、それがセットに含まれているかどうかを確認することです。

于 2014-10-08T22:03:02.103 に答える
1

重複する要素が何であるかを気にしない場合はlen、結合されたリストとセットとして結合されたリストを簡単に確認できます。重複する要素がある場合、セットは短くなります。

len(set(a+b+c))==len(a+b+c) 重複がない場合はTrueを返します。

于 2015-03-10T16:11:06.403 に答える
1

関数型プログラミングスタイルで別のものを投入します。

any(map(lambda x: x in a, b))

説明：

map(lambda x: x in a, b)

bの要素がで見つかったブール値のリストを返しますa。次に、そのリストがに渡されます。このリストは、要素が。であるかどうかをany返すだけです。 TrueTrue

于 2016-11-09T18:08:56.463 に答える