如果两个集合的交集(一个对所有检查都相同,另一个改变)是否为空,我需要做很多检查。
如果支票说(在少量支票中)它不是空的,那没关系,但它是(可以有更精确的第二个过滤步骤),所以误报是可以的。这是不允许的,我过滤掉了肯定有非空交叉点的东西,所以漏报是不行的。
所以,只有一个场景:
{A,B,C,D} <-> {D,E,F} => true
(D in intersection set),绝不允许为假
{A,B,C} <-> {D,E,F} => false
(没有交集),也可以在少量的检查中返回true
对于单个元素,我会使用布隆过滤器,但对于一组元素我找不到类似的东西,布隆过滤器逐个元素检查是一个可能的选择,但我正在寻找更好的东西。
最佳答案
非常感谢您的回答,帮助我想出了一个很好的解决方案并解决了问题。
这个想法基本上很原始,但足够了。
我创建了两个位集,一个用于更改集,一个用于固定集。集合的每个元素都被散列为一位(例如,对于 1 到 64 中的长一位),然后组合成一个集合(主要是 k=1 的 Bloom-Bitset)。
要检查是否存在非空交集,我只需将两个位集与位与运算结合起来,然后检查结果是否不为 0。
假阳性率会(我认为,没有计算)更糟,但对于我的情况来说已经足够了。
例子:
[A,B,C] => 0000100010100000
[B,D,F] => 0100000010000100
--------------------&
0000000010000000 != 0 => 真
关于algorithm - 快速检查交叉点是否设置为空(误报是可以的),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47392972/