optimization - 什么是快速查找集合列表的非空交集的数据结构？

Question

我有一组 N 项，它们是整数集，我们假设它是有序的并称它为 I[1..N]。给定一个 candidate 集，我需要找到 I 的子集，它与 candidate 有非空交集。

因此，例如，如果:

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 和一个变量 candidate 集。目前我通过缓存 items_containing[n] = {the sets which contain 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 的明显示例是 Not Acceptable ，但 N 或 N*log(N) 可以。

Answer 1

我认为您当前的解决方案在大 O 方面是最优的，尽管有微优化技术可以提高其实际性能。例如在将 item_containing 集合中的所选集合与有效项集合合并时使用按位运算。

即您将 items_containing 存储为:

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

你的 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;
}

但它们并没有真正改变 Big-O 的表现。