c++ - 搜索集合数组的更快方法

Question

我有一个包含 100,000 个集合的数组。每组包含 1,000,000 以下的自然数。我必须找到有序对的数量 {m, n}，其中 0 < m < 1,000,000、0 < n < 1,000,000 和 m != n，它们在 100,000 个集合中都不存在。搜索所有集合的简单方法导致 10^5 * (10^6 选择 2) 次搜索。

例如我有 2 组 set1 = {1,2,4} set2 = {1,3}。小于 5 的所有可能的有序数对是 {1,2}、{1,3}、{1,4}、{2,3}、{2,4} 和 {3,4}。在集合 1 中不一起存在的小于 5 的有序数对是 {1,3}、{2,3} 和 {3,4}。第 2 组中缺少的 5 个以下的有序对是 {1,2}、{1,4}、{2,3}、{2,4} 和 {3,4}。两个集合中不一起存在的有序对是 {2,3} 和 {3,4}。所以缺失的有序对数为 2。

谁能指出我组织数据结构的巧妙方法，以便更快地找到缺失对的数量？如果之前有人问过这个问题，我提前道歉。

更新: 这是有关我的数据集结构的一些信息。 每组中的元素数量从 2 到 500,000 不等。元素的中位数约为 10,000。分布在 10,000 左右达到峰值，并在两个方向上逐渐减小。 100,000个集合中元素的并集接近1,000,000。

Answer 1

如果您正在寻找跨 集的组合，有一种方法可以有意义地压缩您的数据集，如 frenzykryger's answer 所示.但是，从您的示例中，您正在寻找的是每个集合内可用的组合数量，这意味着每个集合都包含不可约信息。此外，您也不能使用组合学来简单地从每组中获取组合的数量；您最终希望对所有集合中的组合进行重复数据删除，因此实际组合很重要。

了解这一切之后，很难想出你能取得什么重大突破。假设您有 i 个集合，并且每个集合中最多有 k 个项目。天真的方法是:

• 如果您的集合通常很密集(即包含 1 到 1,000,000 之间的大部分数字)，请将它们替换为集合的补码
• 创建一组 2 个元组(使用确保插入是幂等的集合结构)
• 对于每个集合 O(i):
  • 评估所有组合并插入一组组合:O(k choose 2)

对此的最坏情况复杂度并不高，但假设您有一个集合包含 0 到 1,000,000 之间的大多数数字或几乎不包含任何数字的场景，您应该会看到性能有很大的改进。

另一种方法是继续使用组合学来计算每个集合中的组合数量，然后使用一些有效的方法来查找集合中重复组合的数量。我不知道这种方法，但它可能存在。