algorithm - 比较包含集合的列表部分的高效算法

Question

在我的应用程序中，我需要比较集合列表的各个部分，看看它们是否包含相同的元素。我基本上有以下结构:

List 1 Index   Set
1              (1,5)
2              (3,7)
3              ()
4              (1,9,15)

我有大约 20 个列表，每个列表中有超过 1000 组。列表中的 Sets 可以是空的，也可以包含多达数百个元素。

我需要为列表的不同间隔创建这些集合的并集。因此，例如，我想将前一个列表的间隔与以下列表进行比较:

List 2 Index    Set
1               (3,6,9)
2               (2)
3               (20)

比较区间列表 1 从 2 到 4 和区间列表 2 从 1 到 2 应该得到 (3,9)

目前，我使用的是一种蛮力方法，只需运行两个列表并比较每个集合。有没有更有效的解决方案？

提前致谢

Answer 1

一种方法是为每个这样的列表创建一个辅助列表，其中包含到目前为止出现在集合中的元素的每个索引中的直方图。

在你的例子中:

List Index     histogram
1              [1=1, 5=1]
2              [1=1, 3=1, 5=1, 7=1]
3              [1=1, 3=1, 5=1, 7=1]
4              [1=2, 3=1, 5=1, 7=1, 9=1, 15=1]

现在，给定两个索引，i,j - 您可以通过获取两个直方图来创建索引 i,i+1,...,j 中集合的并集:hist1=list[i-1], hist2=list[j] , 并返回所有元素 x这样 hist1.get(x) < hist2.get(x) , 并在不实际迭代列表的情况下获取并集。

例如，在上面的列表中，如果要查找索引 2,3,4 的并集列表:

hist1=list[1] = [1=1, 5=1]
hist2=list[4] = [1=2, 3=1, 5=1, 7=1, 9=1, 15=1]
hist2-hist1 = [1=2-1, 3=1-0, 5=1-1, 7=1-0, 9=1-0, 15=1-0] = 
            = [1=1, 3=1, 5=0, 7=1, 9=1, 15=1]
union_set = {1,3,7,9,15}

当集合比列表小得多时，这种方法特别有用，这似乎是您的情况。