algorithm - 西方最快的布景操作

Question

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

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

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

感兴趣的: An Implementation of B-Y Intersect

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

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

Answer 1

如果您愿意考虑类似集合的结构，那么 bloom filters具有简单的联合和交叉操作。