18

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

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

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

感兴趣的： BY Intersect 的实现

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

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

4

6 回答 6

4

如果您愿意考虑类似集合的结构，那么布隆过滤器具有微不足道的联合和相交操作。

于 2010-11-23T23:43:34.853 回答
3

对于合理密集的集合，区间列表对于您指定的操作可以击败 O(n)，其中 n 是集合中的元素数。

区间列表本质上是一个严格递增的数字列表，[a1, b1, a2, b2, ..., an, bn]，其中每一对 ai, bi 表示区间 [ai, bi)。严格递增的约束确保每个可描述的集合都有一个唯一的表示。将集合表示为间隔的有序集合允许您的集合操作在每次迭代中处理多个连续元素。

于 2010-11-24T04:58:22.320 回答
2

如果 set 实际上是一个散列集并且两个集合具有相同的散列函数和表大小，那么我们可以跳过仅存在于一个集合中的所有桶。这可能会缩小搜索范围。

于 2010-11-23T22:52:48.997 回答
2

以下论文介绍了在交集大于差 (Z > n/2) 时击败 O(Z) 的有序集的并集、交集和差的算法：

Confluently 持久集和映射

于 2013-01-26T16:18:02.350 回答
1

没有比 O(Z) 更好的解决方案，因为如果您从逻辑上考虑问题，则每个相交、联合和分离算法都必须至少读取所有输入元素一次，所以 Z 读取是必须的。此外，由于默认情况下未对集合进行排序，因此没有进一步的优化可以击败 O(Z)

于 2010-11-23T22:37:48.757 回答
0

抽象地说，集合是支持操作的东西，“X 是一个成员吗？”。您可以根据和定义对交集A n B的操作。一个实现看起来像：AB

interface Set { bool isMember(Object X); };

class Intersection {
    Set a, b;
    public Intersection(Set A, Set B) { this.a = A; this.b = B; }

    public isMember(Object X) {
        return a.isMember(X) and b.isMember(Y);
    }
}

A并且B可以使用显式集合类型来实现，例如 HashSet。每个操作的成本都很便宜，让我们用 O(1) 来近似它；所以交叉路口的成本只有 2 O( n )。;-)

诚然，如果你像这样构建一个大的交集层次结构，检查一个成员可能会更昂贵，对于层次结构中的n 个集合来说，成本可能高达 O( n ) 。对此的潜在优化可能是根据阈值检查层次结构的深度，如果超过阈值则将其具体化为 HashSet。这将降低成员运营成本，并且在应用许多交叉口时可能会摊销建设成本。

于 2010-11-24T00:01:53.610 回答