如何快速查找一组集合中的非空交集，需要使用什么数据结构？

Question

我有一组包含整数的集合，数量为N，假设已经排序并称其为I [1..N]。给定一个candidate集合，我需要找到与candidate存在非空交集的I子集。

例如，如果：

I = [{1,2}, {2,3}, {4,5}]

我希望定义valid_items(items, candidate)，满足以下条件：

valid_items(I, {1}) == {1}
valid_items(I, {2}) == {1, 2}
valid_items(I, {3,4}) == {2, 3}

我正在尝试为给定的一个集合 I 和一个可变的候选集进行优化。目前，我通过缓存 items_containing[n] = {包含 n 的集合} 来实现。在上面的例子中，这将是：

items_containing = [{}, {1}, {1,2}, {2}, {3}, {3}]

即，0不包含在任何项中，1包含在第1个项目中，2包含在第1和第2个项目中，2包含在第2个项目中，3包含在第2个项目中，4和5包含在第3个项目中。

这样，我可以定义valid_items(I, candidate) = union(items_containing[n] for n in candidate)。

是否有更有效的数据结构（可接受的大小）来缓存此联合的结果？明显的空间2^N不可接受，但N或N * log(N)是可以接受的。

- Andrey Fedorov

Answer 1

我认为你目前的解决方案在大O表示法方面是最优的，但是有一些微观优化技巧可以提高其实际性能。例如，在将item_containing集合中选择的集合与有效项目集合合并时使用位运算。

即，将items_containing存储为以下内容：

items_containing = [0x0000, 0x0001, 0x0011, 0x0010, 0x0100, 0x0100]

你可以使用位运算符 OR 来合并 valid_items，例如：

int valid_items(Set I, Set candidate) {
    // if you need more than 32-items, use int[] for valid 
    // and int[][] for items_containing
    int valid = 0x0000;
    for (int item : candidate) {
        // bit-wise OR
        valid |= items_containing[item];
    }
    return valid;
}

但它们并不真正改变大O性能。

- Lie Ryan

Answer 2

一种可能有帮助的表示方法是将集合I存储为大小为n的向量V，其中当i不在V中时，其条目V(i)为0，否则为正数。然后，要取两个向量的交集，您可以将项相乘，要取并集，则将项相加。

- Tom Smith