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

Question

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

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

所以，只有一个场景：

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

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

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

Answer 1

一种优化是保留一个列表（用于快速查找的数组），其中包含每组的最小/最大值。然后首先检查该列表是否重叠。如果不是 -> 返回 false - 不需要进一步检查。

S1: a b c
S2:       d e f

S1 and S2 -> false (no overlap)

如果这些集合已排序并且它们确实重叠，则您只需检查重叠区域。

S1: a b c d e
S2:       d e f g h

Only check the 'd e' region

如果需要检查 2 个以上集合的交集，请首先尝试找到两个不重叠的集合。如果找到->返回 false。如果没有，则仅检查所有这些集合的重叠区域（随着集合的增多，重叠区域应该变得更小）。

S1: a b c d e
S2:       d e f g h
S3:             g h i

S1 and S2 and S3 -> false (S1 and S3 do not overlap)

如果大多数集合的范围很广，您可以使用另一个选项：

假设元素的最大数量为 6400（对于本例），并且每个元素都是或可以转换为 1-6400 的整数。

对于每个集合，可以创建一个小位图（64 位无符号整数），其中一位代表 100 个项目。

例如：

S1: 1,23,80,312,340
S2: 160,184,450
S3: 230,250,340

S1 bitmap: 100100..
S2 bitmap: 010010..
S3 bitmap: 001100..

S1 and S2 -> false
S1 and S3 -> true, only check range 301-400
S1 and S2 and S3 -> false

您当然可以使用小于 100 的数字（最好是 2 的幂，这样您可以快速设置相应的位）并使用多个uint64.

这甚至可以在多个级别上完成（取决于您愿意使用的内存/存储空间量）。例如，首先对一个 64 位整数进行真正的快速检查（需要一个 CPU 周期，并且可以使用 SQL 轻松完成）。仅对于那些匹配的检查，第二级可能包含 4、8 或 16 uint64，每个位代表较小范围的值（使用 SSE/AVX 寄存器也可能非常快）。如果它们仍然匹配，则进行更深入的检查，但仅限于与结果中设置的位相对应的范围。