Python中的成对集合交集

Question

Python中的成对集合交集

16

如果我有一个变量数量的集合（称为 n），每个集合最多有 m 个元素，那么计算所有集合对的交集的最有效方法是什么？请注意，这与所有 n 个集合的交集不同。

例如，如果我有以下集合：

A={"a","b","c"}
B={"c","d","e"}
C={"a","c","e"}

我希望能够找到：

intersect_AB={"c"}
intersect_BC={"c", "e"}
intersect_AC={"a", "c"}

如果这样更容易的话，另一种可接受的格式是将给定集合中的项目映射到包含相同项目的集合。例如：

intersections_C={"a": {"A", "C"},
                 "c": {"A", "B", "C"}
                 "e": {"B", "C"}}

我知道一种方法是创建一个字典，将所有n个集合的并集中的每个值映射到它所出现的集合列表，然后遍历所有这些值来创建类似上面intersections_C的列表，但我不确定随着n增加和集合大小变得太大时，该方法的可扩展性如何。

一些额外的背景信息：

每个集合的长度大致相同，但也非常大（存储它们全部内存中是一个现实的问题，虽然可以使用避免此问题的算法，但不是必需的）
任意两个集合之间的交集大小与集合本身的大小相比非常小
如果有帮助，我们可以假设任何需要输入集合的顺序。

- ankushg

你尝试过你知道有效的方法吗？ - Simeon Visser

我已经在小样本上尝试了我描述的方法，但问题是，我将使用大量用户提供的数据。理想情况下，我希望能够支持更大的用例，因此我想知道是否有比我描述的天真方法更常见/高效的方法可以做到这一点。 - ankushg

1

我认为可以使用哈希表以线性时间完成此操作，与集合大小成线性关系：O(N + M + N * c)，其中c是代表访问哈希表中条目的成本的常数，该常数将与您集合中字符串的长度成比例。 - rendon

我建议使用一个单一的字典来存储所有集合，最终将包含所有元素，因此如果您有大约相同大小的m个n个集合，则其大小为O(n * m)。但是，如果您想要更有见识的猜测，您需要提供更多信息。例如，您只关心n *（n-1）/ 2个交集吗？您能承受额外的O(n * m)空间吗？如果可以，您可以在O(n * m * log(n * m))时间内计算它们---假设您的交集很小；最坏情况下为O(n * n * m * log(n * m))。 - nickie

如果有帮助的话，我们可以假设这些键已经排序。 - ankushg

显示剩余8条评论

3个回答

3

如果我们可以假设输入集是有序的，那么伪归并排序方法似乎很有前途。将每个集合视为排序流，在平行地推进流时，始终只推进那些值是当前所有迭代器中最低的流。每次推进迭代器时，将当前值与新最小值进行比较，并将匹配项转储到相同项集合中。

- tzaman

这是我接下来考虑的事情——字典想法（其中字典以所有n集合的并集为键）似乎更容易理解和实现，但我感觉直观上这会节省一些时间和内存消耗。有什么想法可以量化这种方法相对于字典方法的节省吗？ - ankushg

1

流式处理的主要优势在于您每次只需要在内存中保存一个集合中的一项。而字典处理方法则需要远远超过这个数量： ~O（唯一元素数*平均成员资格）。如果必要，您甚至可以将交集本身写入一组文件中。 - tzaman

-4

使用集合的交集方法怎么样？请看下面：

A={"a","b","c"}
B={"c","d","e"}
C={"a","c","e"}

intersect_AB = A.intersection(B)
intersect_BC = B.intersection(C)
intersect_AC = A.intersection(C)

print intersect_AB, intersect_BC, intersect_AC

- Ajit Vaze

1

我所举的例子旨在提供一个通用的例子（我将会有很多不仅仅是A、B和C），而且如果可能的话，我希望避免重复工作，因为我的集合大小可能非常大。 - ankushg

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- doug · Accepted Answer

这可以满足你的需求。

import random as RND
import string
import itertools as IT

模拟一些数据

fnx = lambda: set(RND.sample(string.ascii_uppercase, 7))
S = [fnx() for c in range(5)]

生成S集合中的索引列表，以便下面更简洁地引用这些集合。

idx = range(len(S))

获取S中所有可能的唯一项目对; 由于集合交集是可交换的，因此我们想要组合而不是排列

pairs = IT.combinations(idx, 2)

写一个函数，执行集合的交集操作。

nt = lambda a, b: S[a].intersection(S[b])

将此函数对每个键值对进行折叠，并将每个函数调用的结果与其参数关联。

res = dict([ (t, nt(*t)) for t in pairs ])

以下结果按照OP中第一种选项格式化，是一个字典，其中values为两个序列的交集；每个值都被分类到由这些序列的两个索引组成的元组中。

这个解决方案只需要两行代码：(i) 计算排列组合; (ii) 然后在每个排列上应用某些函数，将返回的值存储在结构化容器（键-值）容器中。

该解决方案的内存占用极小，但您可以通过在最后一步返回生成器表达式来做得更好，即

res = ( (t, nt(*t)) for t in pairs )

请注意，使用这种方法，既没有将成对的顺序也没有相应的交集写入内存中--即，pairs和res都是迭代器。