3

我有一组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是不可接受的，但N或N*log(N)将是。

4

2 回答 2

2

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

即您将 items_ contains 存储为：

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

并且您的 valid_items 可以使用按位 OR 来合并，如下所示：

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 的性能。

于 2010-04-06T23:11:03.583 回答
1

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

于 2010-04-06T23:07:39.693 回答