python - 集合列表的减法

Question

给定一个集合列表:

allsets = [set([1, 2, 4]), set([4, 5, 6]), set([4, 5, 7])]

计算不与其他集合重叠的相应元素集合列表的 Pythonic 方法是什么？

only = [set([1, 2]), set([6]), set([7])]

有没有办法通过列表理解来做到这一点？

Answer 1

为避免二次运行时间，您需要进行初始传递以找出哪些元素出现在多个集合中:

import itertools
import collections
element_counts = collections.Counter(itertools.chain.from_iterable(allsets))

然后你可以简单地制作一个集合列表，保留所有只出现一次的元素:

nondupes = [{elem for elem in original if element_counts[elem] == 1}
            for original in allsets]

---

或者，不是直接从 element_counts 构造 nondupes，我们可以进行额外的传递以构造一组恰好出现在一个输入中的所有元素。这需要一个额外的语句，但它允许我们利用 & 运算符进行集合交集，使列表理解更短、更高效:

element_counts = collections.Counter(itertools.chain.from_iterable(allsets))
all_uniques = {elem for elem, count in element_counts.items() if count == 1}
#                                                     ^ viewitems() in Python 2.7
nondupes = [original & all_uniques for original in allsets]

时间似乎表明使用 all_uniques 集可以显着加快整个重复消除过程。对于重度重复的输入集，Python 3 上大约为 3.5x speedup，但由于更多的运行时间由构建计数器控制，因此 Python 2 上的整体重复消除过程只有大约 30% speedup。这种加速是相当可观的，尽管不如首先使用 element_counts 避免二次运行时间那么重要。如果您使用的是 Python 2 并且这段代码对速度要求很高，那么您会希望使用普通的 dict 或 collections.defaultdict 而不是 Counter 。

另一种方法是从 element_counts 构造一个 dupes 集并使用 original - dupes 而不是 original & all_uniques 在列表理解中，如 munk 的 suggested。这是否比使用 all_uniques 集和 & 表现更好或更差取决于您输入的重复程度以及您使用的 Python 版本，但它 doesn't seem无论哪种方式都会产生很大的不同。