algorithm - 整数列表的子集计算

Question

我目前正在实现一种算法，其中一个特定步骤要求我按以下方式计算子集。

假设我有一组(可能有数百万个)整数。每个集合可能包含大约 1000 个元素:

Set1: [1, 3, 7]
Set2: [1, 5, 8, 10]
Set3: [1, 3, 11, 14, 15]
...,
Set1000000: [1, 7, 10, 19]

想象一个特定的输入集:

InputSet: [1, 7]

我现在想快速计算出这个InputSet 是哪个子集。在这种特殊情况下，它应该返回 Set1 和 Set1000000。

现在，暴力破解需要太多时间。我还可以通过 Map/Reduce 并行化，但我正在寻找更智能的解决方案。此外，在某种程度上，它应该具有内存效率。我已经通过使用 BloomFilters 来快速消除输入集永远不可能成为其子集的集来优化计算。

我错过了什么聪明的技巧吗？

谢谢!

Answer 1

好吧 - 看来瓶颈在于集合的数量，因此您可以通过从元素映射到包含它们的所有集合并返回包含所有元素的集合来增强性能，而不是通过迭代所有集合来查找集合。您搜索的元素。

这与搜索 inverted index 时 AND 查询中所做的非常相似。在information retrieval领域.

在您的示例中，您将拥有:

1 -> [set1, set2, set3, ..., set1000000]
3 -> [set1, set3]
5 -> [set2]
7 -> [set1, set7]
8 -> [set2]
...

编辑:
在IR的倒排索引中，为了节省空间，我们有时使用d-gaps - 这意味着我们存储文档之间的偏移量而不是实际的数字。例如，[2,5,10] 将变为 [2,3,5]。这样做并使用 delta encoding当涉及到空间时，用数字来表示往往会有很大帮助。
(当然也有一个缺点:你需要读取整个列表才能查找特定的集合/文档是否在其中，并且不能使用二分搜索，但有时这是值得的，特别是如果它是将索引装入 RAM 与不装入 RAM 之间的区别)。