小编Pet*_* V.的帖子

快速检查交集是否设置为空(误报是可以的)

如果两组的交集(一组对所有检查相同,另一组更改)是否为空,我需要进行大量检查。

如果支票说(在少量支票中)它不是空的,那没关系,但它是(可以有更精确的第二个过滤步骤),所以误报是可以的。这是不允许的,我过滤掉了肯定有非空交叉点的东西,所以假阴性是不行的。

所以,只有一个场景:

{A,B,C,D} <-> {D,E,F} => true (D 在交集),永远不允许为假

{A,B,C} <-> {D,E,F} => false (无交集),也可以在少量检查中返回 true

对于单个元素,我将使用布隆过滤器,但我找不到一组元素的类似内容,并且可以选择逐个元素检查布隆过滤器,但我正在寻找更好的方法。

algorithm probability bloom-filter data-structures

5
推荐指数
1
解决办法
570
查看次数