在Python中减去两个列表

Question

在Python中，如何从两个不唯一且无序的列表中减去元素呢？比如我们有 a = [0,1,2,1,0] 和 b = [0, 1, 1]，我想做类似 c = a - b 的操作，结果 c 应该是 [2, 0] 或者 [0, 2]，顺序对我来说无所谓。如果 a 中不包含 b 的所有元素，应该抛出一个异常。

注意，这和集合是不同的！ 我并不是想找出 a 和 b 中元素集合的差异，而是想找出 a 和 b 中实际元素的差异。

我可以用一个循环来实现，先在 a 中查找 b 的第一个元素，然后把这个元素从 b 和 a 中删除，依此类推。但我觉得这样做不太好，因为效率很低（时间复杂度是 O(n^2)），而实际上应该可以在 O(n log n) 的时间内完成这个操作。

Answer 1

我会用更简单的方法来做：

a_b = [e for e in a if not e in b ]

..正如上面提到的，这样做是不对的——只有当列表中的项目是唯一的时候才有效。如果项目是唯一的，使用下面的方法会更好：

a_b = list(set(a) - set(b))

Answer 2

我知道“for”不是你想要的，但它简单明了：

for x in b:
  a.remove(x)

或者如果b里的成员可能不在a里，那就用：

for x in b:
  if x in a:
    a.remove(x)

Answer 3

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 源代码。