3

我有许多带有排序数据的数组。我需要在这个数组中执行二进制搜索。如果此数组中的键范围不相交，则可以按范围对数组进行排序，然后像使用单个数组一样执行二进制搜索。但就我而言，这个数组中的键范围可以重叠。在这种情况下，只能执行过滤以排除某些数组，然后对另一部分进行排序。在我的情况下，大多数数组不重叠，所以过滤，大多数时候，只会返回一个数组，但坏数据仍然有可能破坏性能。

在这种情况下是否可以使用更好的算法？可以稍微修改数组，添加一些元数据或链接到其他数组。

更新 此阵列是由磁盘存储支持的数据页。我为此使用内存映射文件。我可以非常快速地对页面内的数据进行排序，因为此过程不涉及复制。但是要合并两个页面，我需要在页面之间复制大量数据。我有非常大量的数据，TB！但是每页只有8Mb，所以可以快速搜索。不时添加到存储中的新页面。Pages 包含时间序列数据，因此它已经部分排序，并且新数组在大多数情况下不会与旧数据重叠。

4

5 回答 5

4

如果此数组中的键范围不相交，则可以按范围对数组进行排序，然后像使用单个数组一样执行二进制搜索。但就我而言，这个数组中的键范围可以重叠。

你仍然可以对它们进行排序。您可以使用区间树来存储它们并以对数时间检索要搜索的数组，而不是简单地按边界过滤所有数组。由于您有很多数组并且它们很少相互重叠，因此这应该会显着提高性能。

于 2013-10-01T16:02:21.703 回答
2

如果您只计划执行一些查询，我认为您无法改进您的算法 - 我相信它已经相当不错了。如果您希望执行大量查询，我建议您将数组合并为一个数组并对其执行二进制搜索。合并与归并排序的算法相同，并且是线性的。因此，只要查询的数量弥补了线性合并，它就是值得的。

于 2013-10-01T13:51:35.850 回答
2

8MB 页面中的 TB 意味着您可以处理几百万个页面。每个页面都在内部排序，页面中的值可以（很少，但它们可以）相互重叠。

我希望找到正确页面的影响高于在页面中找到正确的条目。

因此，我推荐以下方法：

  • 维护一个每页具有最低和最高键的数组（lowestPageKey, highestPageKey）。
  • 进行二分搜索以获得合适的页面，并在页面内进行第二次二分搜索。
  • 为了找到合适的页面，searchKey请在元数据中进行范围拟合二进制搜索。
    • 使用条件lowestPageKey <= searchKey <= highestPageKey找到正确的页面。
    • 如果lowestPageKey > searchKey您可以继续使用数组的下半部分
    • 如果highestPageKey < searchKey您可以继续使用数组的上半部分

这样，您将找到正确的页面，并可以在找到的页面中进行第二次二进制搜索。

我这边的另一个问题：如果页面中的值重叠，您可以找到多个包含搜索键的条目（或多个页面）。在这种情况下，您期望得到什么？随机一页/条目，所有页面/条目，第一页/最后一页/条目或错误消息？

于 2013-10-07T12:33:29.750 回答
2

您暗示您对大多数静态数据有很多查询，所以我会假设。你在正确的轨道上。只是不要排除重叠的数组。跟踪重叠。这里是如何。首先编译范围索引。如果阵列是不相交的，它们将是块。当您有两个数组重叠时：

|     A    |
     |       B       |

分为三个范围：

| A  | AB  |   B     |

如图所示，范围索引只记录下限和上限以及覆盖该范围的数组列表。

现在搜索索引（在内存中）以确定要搜索的数组。然后去搜索所有这些。作为进一步的优化，可以使用块边界来限制数组搜索。换句话说，如果你得到上面的块 AB，你可以在搜索时排除 A 的一部分和 B 的一部分。

如何高效地编译和更新索引？我建议使用区间树。此页面提供伪代码。如果您使用 C++ 进行编程，则可以使用相关的 Boost 库来获得优势。

对于区间树，每个数组都是一个区间。当你用一个点查询树时，你会得到所有相关的区间。这些是需要搜索的数组。

于 2013-10-10T03:07:55.743 回答
1

维护具有不相交范围的多组数组。

执行二分搜索时，在这些组上并行执行，或者在基于最小优先的组上尝试。

对于每个组，维护范围，每当新页面到达时，将其附加到与该新页面没有不相交范围的最大组。如果页面不属于任何组，请创建一个新的。

正如您所说，大多数情况下范围不重叠，拥有这些额外组的机会要少得多，但是当这种异常发生时，算法可以适应。

于 2013-10-13T12:07:38.950 回答