2

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

想象一下，我有一组（可能是数百万个）整数。每个集合可能包含大约 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 来优化计算，以快速消除输入集永远不可能是子集的集。

我错过了什么聪明的技术？

谢谢！

4

4 回答 4

2

嗯 - 似乎瓶颈是集合的数量，所以不是通过迭代所有集合来找到一个集合，您可以通过从元素映射到包含它们的所有集合来提高性能，并返回包含您搜索的所有元素的集合为了。

这与在信息检索领域搜索倒排索引时的AND查询非常相似。

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

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

编辑：
在 IR 的倒排索引中，为了节省空间，我们有时会使用d-gaps - 这意味着我们存储文档之间的偏移量而不是实际数字。例如，[2,5,10]将成为[2,3,5]. 这样做并使用增量编码来表示数字在空间方面往往有很大帮助。
（当然也有一个缺点：您需要阅读整个列表才能找到其中是否有特定的集合/文档，并且不能使用二进制搜索，但有时值得，特别是如果它是拟合之间的差异是否索引到 RAM 中）。

于 2013-01-02T14:21:09.893 回答
0

如何存储包含每个数字的集合列表？

1 -- 1, 2, 3, 1000000
3 -- 1, 3
5 -- 2
etc.
于 2013-01-02T14:21:33.577 回答
0

  1. 从输入集的最大数 (7) 开始搜索并消除其他子集（将返回 Set1 和 Set1000000）。

  2. 在剩余集合中搜索其他输入元素 (1)。

于 2013-01-02T15:32:09.303 回答
0

扩展 amit 的解决方案，而不是存储实际数字，您可以只存储间隔及其相关集。

例如使用 5 的间隔大小：

 (1-5): [1,2,3,1000000]
 (6-10): [2,1000000]
 (11-15): [3]
 (16-20): [1000000]

在 (1,7) 的情况下，您应该考虑区间 (1-5) 和 (5-10)（这可以通过知道区间的大小简单地确定）。与这些范围相交会得到 [2,1000000]。集合的二分搜索表明，确实，(1,7) 存在于两个集合中。

尽管您需要检查每个集合的最小值和最大值，以更好地了解间隔大小应该是多少。例如，如果最小值和最大值从 1 变为一百万，则 5 可能是一个糟糕的选择。

您可能应该保留它，以便可以使用二进制搜索来检查值，因此子集范围应该类似于 (min + max)/N，其中 2N 是需要二进制搜索的最大值数每组。例如，“集合 3 是否包含从 5 到 10 的任何值？” 这是通过找到最接近 5 (3) 和 10 (11) 的值来完成的，在这种情况下，不，它没有。您必须遍历每个集合并对可能在集合内的间隔值进行二进制搜索。这意味着确保当集合仅达到 10 时，您不会去搜索 100。

您也可以只存储范围（最小值和最大值）。但是，问题是我怀疑您的数字会被聚集在一起，因此没有太多用处。尽管如前所述，它可能对确定如何设置间隔很有用。

选择使用什么范围还是很麻烦的，太大了，构建数据结构需要很长时间（1000 *million * log(N)）。太小了，你会开始遇到空间问题。范围的理想大小可能是这样的：它确保与每个范围相关的集合的数量大致相等，同时还确保范围的总数不会太高。

编辑：一个好处是您实际上不需要存储所有间隔，只需要存储您需要的间隔。虽然，如果您有太多未使用的间隔，明智的做法可能是增加间隔并拆分当前间隔以确保搜索速度快。如果游行时间不是主要问题，则尤其如此。

于 2013-01-02T15:34:48.903 回答