我在一个地方找不到任何令人满意的关于这个话题的报道,所以我想知道:
最快的集合相交、并集和分离算法是什么?
有没有域名有限的有趣的网站?
有人能在z是交叉点实际大小的地方,打败o(z)吗?
如果您的方法依赖于排序集,请注意,但不要将其视为不合格因素。在我看来,必须有一个真正的仓库微妙的优化共享,我不想错过任何一个。
我知道的一些算法依赖于非常规的按位操作,所以您可以假设SSE4的存在和对POPCount等内部函数的访问。请注意这个假设。
感兴趣的:
An Implementation of B-Y Intersect
更新
我们得到了一些非常好的部分答案,但我仍然希望对这个问题进行更全面的攻击。我特别感兴趣的是看到一个更充分的使用布卢姆过滤器来解决这个问题。
更新
我已经做了一些关于布卢姆过滤器和布谷鸟哈希表结合的初步工作。它看起来几乎令人讨厌,因为他们有着非常相似的需求。我已经接受了一个答复,但我现在还不太满意。
最佳答案
如果您愿意考虑类似集合的结构,那么bloom filters具有平凡的并集和相交运算。