[解決済み] リスト内の複数の値のメンバーシップをテストするには？

質問

2つ以上の値がリスト上でメンバーシップを持つかどうかをテストしたいのですが、予期しない結果が得られます。

>>> 'a','b' in ['b', 'a', 'foo', 'bar']
('a', True)

では、Pythonはリスト内で一度に複数の値のメンバーシップをテストできるのでしょうか？ その結果はどのような意味を持つのでしょうか？

解決方法は？

これは、あなたが望むことを実現し、ほぼすべてのケースで動作します。

>>> all(x in ['b', 'a', 'foo', 'bar'] for x in ['a', 'b'])
True

式は 'a','b' in ['b', 'a', 'foo', 'bar'] は期待通りに動作しません。Pythonはこれをタプルとして解釈するからです。

>>> 'a', 'b'
('a', 'b')
>>> 'a', 5 + 2
('a', 7)
>>> 'a', 'x' in 'xerxes'
('a', True)

その他のオプション

このテストを実行する方法は他にもありますが、これほど多くの種類の入力に対して機能するわけではありません。例えば カビー この問題は、集合を使って解決することができるのですが...。

>>> set(['a', 'b']).issubset(set(['a', 'b', 'foo', 'bar']))
True
>>> {'a', 'b'} <= {'a', 'b', 'foo', 'bar'}
True

...することがあります。

>>> {'a', ['b']} <= {'a', ['b'], 'foo', 'bar'}
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

セットは、ハッシュ化可能な要素でのみ作成可能です。しかし、ジェネレータ式 all(x in container for x in items) は、ほとんどすべてのコンテナ型を扱うことができます。唯一の要件は container は再反復可能である（すなわち、生成器ではない）。 items は、任意の反復可能であることができます。

>>> container = [['b'], 'a', 'foo', 'bar']
>>> items = (i for i in ('a', ['b']))
>>> all(x in [['b'], 'a', 'foo', 'bar'] for x in items)
True

スピードテスト

多くの場合、サブセットテストは all しかし、その差は衝撃的なものではありません。ただし、集合が選択肢にないため、質問に無関係な場合を除きます。このようなテストのためだけにリストを集合に変換することは、いつも手間に見合うとは限りません。また、ジェネレータを集合に変換することは、時には信じられないほど無駄で、プログラムの速度を何桁も低下させることがあります。

以下に、説明のためのベンチマークをいくつか示します。最も大きな違いは container と items は比較的小さい。その場合、サブセット・アプローチの方が1桁ほど速くなる。

>>> smallset = set(range(10))
>>> smallsubset = set(range(5))
>>> %timeit smallset >= smallsubset
110 ns ± 0.702 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)
>>> %timeit all(x in smallset for x in smallsubset)
951 ns ± 11.5 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

これは大きな違いのように見えます。しかし container はセットです。 all は、はるかに大きなスケールでも完全に使用可能です。

>>> bigset = set(range(100000))
>>> bigsubset = set(range(50000))
>>> %timeit bigset >= bigsubset
1.14 ms ± 13.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
>>> %timeit all(x in bigset for x in bigsubset)
5.96 ms ± 37 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

サブセット・テストの方がまだ速いですが、この規模では5倍程度に過ぎません。この速度は、Pythonの高速な c -の実装をバックアップしています。 set しかし、基本的なアルゴリズムはどちらも同じです。

もし、あなたの items が他の理由ですでにリストに格納されている場合、サブセット・テストのアプローチを使用する前にそれらをセットに変換する必要があります。そうすると、スピードアップは2.5倍程度に落ちます。

>>> %timeit bigset >= set(bigsubseq)
2.1 ms ± 49.2 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

そして、もしあなたの container がシーケンスであり、最初に変換する必要がある場合、スピードアップはさらに小さくなります。

>>> %timeit set(bigseq) >= set(bigsubseq)
4.36 ms ± 31.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

悲惨なほど遅い結果が出るのは、放置したときだけです container をシーケンスとして使用します。

>>> %timeit all(x in bigseq for x in bigsubseq)
184 ms ± 994 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

もちろん、どうしてもそうしなければならない場合だけですが。の項目がすべて bigseq がハッシュ化可能であれば、代わりにこうします。

>>> %timeit bigset = set(bigseq); all(x in bigset for x in bigsubseq)
7.24 ms ± 78 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

これは、代替案よりもちょうど1.66倍速い( set(bigseq) >= set(bigsubseq) 4.36で計測）。

つまり、サブセットテストは一般的に高速ですが、驚くほどの差はないのです。一方、次のような場合を見てみましょう。 all が速くなります。もし items は1千万個の値を持ち、その中には container ?

>>> %timeit hugeiter = (x * 10 for bss in [bigsubseq] * 2000 for x in bss); set(bigset) >= set(hugeiter)
13.1 s ± 167 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
>>> %timeit hugeiter = (x * 10 for bss in [bigsubseq] * 2000 for x in bss); all(x in bigset for x in hugeiter)
2.33 ms ± 65.2 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

ジェネレーターをセットに変換することは、この場合、非常に無駄が多いことがわかります。その set コンストラクタはジェネレータ全体を消費しなければなりません。しかし、短絡的な動作である all は、ジェネレータのごく一部しか消費する必要がないことを保証しています。 4桁 .

これは極端な例であることは認めざるを得ません。しかし、これが示すように、すべてのケースでどちらかのアプローチがより高速であると仮定することはできません。

アップショット

ほとんどの場合 container をセットに変換することは、少なくともその要素がすべてハッシュ化可能である場合には、価値があります。というのも in はO(1)であるのに対し、集合に対する in 配列の場合、O(n)である。

一方、サブセット・テストの利用は、おそらく時々しか価値がありません。テスト項目がすでにセットで保存されている場合は、間違いなくそれを行います。そうでない場合は all は少し遅いだけで、追加のストレージは必要ありません。また、アイテムの大規模なジェネレータで使用することもでき、その場合は大幅なスピードアップを実現することもあります。