问题标签 [set-intersection]

给定两个列表（不一定是排序的），找到这些列表的集合交集的最有效的非递归算法是什么？
我不相信我可以使用散列算法。

给定具有多个属性的对象列表，我需要找到由所有相交子集的并集创建的集合列表。

具体来说，这些是 Person 对象，每个对象都有许多属性。我需要根据一些唯一标识符（如 SSN、DLN 等）创建一个“主”集列表。

例如，如果人 A 和人 B 具有相同的 SSN，他们会创建一个集合 i。然后如果人 B 和 C 有相同的 DLN，他们创建一个集合 ii。人员 D 和 E 具有相同的 SSN，但它（以及所有其他标识符）与人员 A、B 或 C 的任何标识符都不匹配。合并所有相交的子集后，我最终会得到一组人员 A、B、C和另一组人 D、E。

这是我的解决方案的伪代码。我很好奇是否有人已经提出了一种更有效的方法来合并所有可能的相交集。请记住，集合之间的链接可能是 X 个人长（即 A 通过 SSN 匹配 B，B 通过 DLN 匹配 C，C 通过 SSN 匹配 D，并且 D 通过其他标识符匹配 E，这将导致 Persons AE 在一个集合中）。还假设将在其中实现的语言支持集合操作。

假设我们有一个data1和data2。我怎样才能与它们相交std::set_intersect()？

我有一个集合列表：

我想要 s1 ∩ s2 ∩ s3 ...

我可以通过执行一系列 pairwises1.intersection(s2)等来编写一个函数来完成它。

有推荐的、更好的或内置的方式吗？

以前没有使用过 set_intersection，但我相信它可以与地图一起使用。我编写了以下示例代码，但它并没有给我我所期望的：

由于标记为 (3) 和 (4) 的对出现在两个地图中，我希望我会在交叉路口获得 2 个元素，但不，我得到：

我确定这与地图/对上的比较器有关，但无法弄清楚。

从我的问题

以升序将元素插入到 ArrayList 并且没有重复元素

我已经完成了我的插入方法。

现在我尝试找出如何构建并集、交集和差分方法来对 2 个 IntSet 进行操作。

请注意，IntSet 的元素数量很大，我需要在O(m+n)时间内完成，其中 m 和 n 是两个 IntSet 的元素数量。

例如 IntSet

我该怎么做？

PS它可以使用归并排序吗？

编辑：

这是我的联合代码

我花了相当多的时间为我的一个应用程序编写 Baeza-Yates 的快速集合交集算法。虽然我在 STL set_intersect 上做的稍微好一点，但在对输出进行排序后，我从实现自己的算法中获得的任何时候都需要对结果集进行排序这一事实被删除。鉴于 STL set_intersect 表现良好，任何人都可以指出它实际实现的算法吗？或者它是否实现了相同的 Baeza-Yates 算法，但只是以更有效的方式？

Baeza-Yates：http ://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.91.7899&rep=rep1&type=pdf

目前，我认为我最好的选择是使用std::set_intersection，然后检查较小输入的大小是否与set_intersection填充的元素数相同。

有更好的解决方案吗？

我无法在一个地方找到任何令人满意的关于这个主题的报道，所以我想知道：最快的集合相交、联合和分离算法是什么？
有没有一些有趣的域名有限的？
任何人都可以击败 O(Z)，其中 Z 是交叉点的实际大小？

如果您的方法依赖于排序集，请注意这一点，但不要将其视为取消资格的因素。在我看来，必须有一个名副其实的微妙优化库要共享，我不想错过任何一个。

我知道的一些算法依赖于原版之外的按位运算，因此您可以假设存在 SSE4 并可以访问诸如 popcount 之类的内在函数。请注意这个假设。

感兴趣的： BY Intersect 的实现

更新
我们已经得到了一些非常好的部分答案，但我仍然希望对这个问题进行更完整的攻击。我特别有兴趣看到更全面地使用布隆过滤器来解决问题。

更新
我已经完成了一些将布隆过滤器与布谷鸟哈希表结合起来的初步工作。它看起来几乎令人讨厌，因为他们有非常相似的要求。我已经接受了答案，但目前我并不满意。

有没有一种算法，给定两个集合，在线性时间内计算它们的交集？

我可以运行两个for循环来检查所有元素对，记录我在两个集合中找到的元素。但是，运行时间将为 O(n ² )。我如何在 O(n) 时间内做到这一点？