我目前正在实现一个算法，其中一个特定的步骤要求我以以下方式计算子集。
假设我有一组（可能有数百万个）整数其中每个集合可能包含大约1000个元素：
Set1: [1, 3, 7]
Set2: [1, 5, 8, 10]
Set3: [1, 3, 11, 14, 15]
...,
Set1000000: [1, 7, 10, 19]
设想一个特定的输入集：
InputSet: [1, 7]
我现在想快速计算这个输入集是哪个子集在这种特殊情况下，它应该返回set1和set1000000。
现在，暴力逼迫需要太多时间我也可以通过map/reduce并行，但我正在寻找一个更智能的解决方案。而且，在一定程度上，它应该是内存高效的。我已经通过使用bloomfilters优化了计算，以快速消除输入集不能成为子集的集。
我错过了什么聪明的技巧吗？
谢谢！
最佳答案
好吧-瓶颈似乎是集合的数量，所以您可以通过从元素到包含它们的所有集合的映射来提高性能，并返回包含您搜索的所有元素的集合，而不是通过遍历所有集合来找到集合。
这与在inverted index字段中搜索information retrieval时在和查询中执行的操作非常相似。
在您的示例中，您将拥有：
1 -> [set1, set2, set3, ..., set1000000]
3 -> [set1, set3]
5 -> [set2]
7 -> [set1, set7]
8 -> [set2]
...
编辑：
在IR的倒排索引中，为了节省空间，我们有时使用d-间隙-这意味着我们存储文档之间的偏移量，而不是实际的数字例如，
[2,5,10]将变为[2,3,5]。这样做和使用delta encoding来表示数字往往对空间有很大帮助。（当然也有一个缺点：您需要阅读整个列表，以便找到其中是否有特定的集合/文档，并且不能使用二进制搜索，但有时它是值得的，尤其是在索引是否适合RAM之间的差异）。
关于algorithm - 整数列表的子集计算，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14123595/