[解決済み】Pythonで2つのリストを引き算する

質問

Pythonで、2つの一意でない順序付きリストを引き算するにはどうしたらよいでしょうか？私たちが持っているとしましょう a = [0,1,2,1,0] と b = [0, 1, 1] のようなことをしたい。 c = a - b を持ち c である [2, 0] または [0, 2] の順番はどうでもいいんです。これは、aがbのすべての要素を含んでいない場合、例外を投げる必要があります。

これはセットとは異なることに注意してください aとbの要素の集合の差を求めるのではなく、aとbの要素の実際の集まりの差に興味があるのです。

forループで、aの中のbの最初の要素を調べて、bとaから要素を取り除く、などということができますね。しかし、これは私には魅力的ではありません、非常に非効率的でしょう（順序が O(n^2) で行うのは問題ないはずなのに、時間がかかる。 O(n log n) 時間です。

解決方法は？

Python 2.7と3.2には collections.Counter クラスは、要素をその要素の出現回数に対応させる辞書のサブクラスです。 これは多重集合として使うことができる。次のようなことができます。

from collections import Counter
a = Counter([0, 1, 2, 1, 0])
b = Counter([0, 1, 1])
c = a - b  # ignores items in b missing in a

print(list(c.elements()))  # -> [0, 2]

の各要素が正しく動作していることを確認したい場合にも、同様に b は a :

# a[key] returns 0 if key not in a, instead of raising an exception
assert all(a[key] >= b[key] for key in b)

しかし、あなたは2.5から抜け出せないので、それをインポートして、それが失敗した場合に独自のバージョンを定義することを試みてはどうでしょうか。 そうすれば、最新版があれば確実に入手できるし、そうでなければ動作するバージョンにフォールバックすることができる。また、将来的にC言語の実装に変換された場合、速度向上の恩恵を受けることができます。

try:
   from collections import Counter
except ImportError:
    class Counter(dict):
       ...

現在のPythonのソースを見ることができます ここで .