algorithm - 删除作为子集的集合

Question

假设您有两个整数集列表。称它们为 A 和 B。A 中的每个集合都可以包含在 B 中的一个集合中。找到 A 中的所有元素以致所有元素都不包含在 B 的集合中的最有效算法是什么？

Answer 1

要尝试缩小搜索空间，我们可以尝试将一些检查和过滤器作为搜索的一部分。以评论中的示例为例，

A = [{1,2},{1,4},{3,4,7}]
B = [{2,3,4},{1,2,4},{1,2,5,6}] 

从集合中唯一元素的 O(n) 枚举开始，作为指向它们所属集合的互相关索引的键:

1: A: {0,1}, B: {1,2}
2: A: {0}  , B: {0,1,2}
3: A: {2}  , B: {0}
4: A: {1,2}, B: {0,1}
5: A: {}   , B: {2}
6: A: {}   , B: {2}
7: A: {2}  , B: {}

我们可以立即在 A 中留出包含 B 中没有的元素的集合，例如 A 的第三个集合。

现在，我们将遍历 A 中未被排除的每个集合，并检查 B 中是否存在至少一个集合的相应完整交集。由于您的案例中的集合索引数量为数百万，与其一开始遍历 B，不如将 B 的检查分成几个部分，每个部分 k 集合，比如 1024。此外，为了表示这 1024 个集合索引，我们将把它们分成 16每个 64 位的位集，因此我们可以按位与 (&) 一个与另一个。

在此遍历期间的任何时候，如果 AND 运算结果为零，我们将受益于提前退出:

set A[0] => elements 1,2 => set-index-intersection in B: b110 & b111 => match
set A[1] => elements 1,4 => set-index-intersection in B: b110 & b11  => match

总的来说，逐个部分地工作，我们正在查看大约 10 * 16 个操作来检查 A 中的一个集合是否包含在 k B 集合的当前部分中的集合之一中.换句话说，我们已经将操作次数从 10,000,000 次减少到 160,000 次以完整检查 A 中的一组(B 中的每百万组)。这是 62 的因数。