什么是快速查找的集列表的非空交叉点的数据结构？

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被包含在itmes 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)将是

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

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

Answer 2

一个表示可能有助于被存储组I为大小为n，其条目Ⅴ的矢量V（i）为0时i不是在V和否则阳性。然后采取两个矢量乘法你的术语的交叉点，并采取联合添加的条款。