2

我有一个包含 20 个数字（64 位整数）的数组，例如 10、25、36,43....、118、121（排序后的数字）。

现在，我必须输入数百万个数字（比如 17、30）。

我必须作为输出给出的是：

for Input 17:

17 is < 25 and > 10. So, output will be index 0.

for Input 30:

30 is < 36 and > 25. So, output will be index 1.

现在，我可以使用线性搜索、二元搜索来做到这一点。有什么方法可以更快地做到这一点吗？输入数字是随机的（高斯）。

4

5 回答 5

6

如果您知道分布，您可以以更智能的方式指导您的搜索。

这是这种二分搜索变体的粗略想法：

假设您的数据预计将均匀分布在 0 到 100 上。

如果观察到值 0，则从头开始。如果你的值是 37，你从你拥有的数组的 37% 开始。这是二分搜索的关键区别：您并不总是从 50% 开始，而是尝试从预期的“最佳”位置开始。

如果您知道参数，这也适用于高斯分布数据（如果您不知道它们，您仍然可以从观察到的数据中轻松估计它们）。您将计算高斯 CDF，这会产生开始搜索的位置。

现在，对于下一步，您需要优化您的搜索。在你看到的位置，有一个不同的值。您可以使用它来重新估计位置以继续搜索。

现在，即使您不知道分布，这也可以很好地工作。因此，您从二分搜索开始，已经查看了 50% 和 25% 的对象。如果您的查询值非常接近 50% 条目，那么您可以做一个更好的猜测，而不是下一步去 37.5% 。除非您的数据集非常“笨拙”（并且您的查询与数据不相关），否则这仍然应该优于始终在中间分裂的“幼稚”二进制搜索。

http://en.wikipedia.org/wiki/Interpolation_search

来自维基百科的预期平均运行时间显然是O(log(log(n))。

更新：因为有人抱怨只有 20 个数字，情况就不一样了。是的，他们是。使用 20 个数字进行线性搜索可能是最好的。因为 CPU 缓存。通过少量内存（适合 CPU 缓存）进行线性扫描可以非常快。特别是展开循环。但是，恕我直言，这种情况非常可悲且无趣。

于 2013-02-09T08:48:48.480 回答
2

没有什么比binary search您的数组已排序更好的了。

线性搜索是O(n)，而二分搜索是O(log n)

编辑：

插值搜索做了一个额外的假设（元素必须是均匀分布的）并且每次迭代进行更多的比较。

您可以同时尝试并根据经验衡量哪个更适合您的情况

于 2013-02-09T08:47:32.720 回答
2

我相信对您来说最好的选择是使用upper_bound - 它会发现数组中的第一个值大于您正在搜索的值。

仍然取决于您尝试解决的问题，也许lower_bound或binary_search可能是您需要的。

所有这些算法都具有对数复杂度。

于 2013-02-09T08:54:06.977 回答
2

事实上，这个问题很有趣，因为它是一个信息论框架的重铸。

给定 20 个数字，您最终将得到 21 个 bin（包括 < 第一个和 > 最后一个）。

对于每个传入号码，您将映射到这 21 个垃圾箱之一。这种映射是通过比较完成的。每次比较都会为您提供 1 位信息（< 或 >= -- 两种状态）。

所以假设传入的数字需要5次比较才能确定它属于哪个bin，那么就相当于用5位来表示那个数字。

我们的目标是尽量减少比较次数！我们有 100 万个数字，每个数字属于 21 个有序的代码字。我们如何做到这一点？

这正是熵压缩问题。

让 a[1],.. a[20] 成为你的 20 个数字。

设 p(n) = pr { 传入号码 < n }。

构建决策树如下。

Step 1.

   let i = argmin |p(a[i]) - 0.5|

   define p0(n) = p(n) / (sum(p(j), j=0...a[i-1])), and p0(n)=0 for n >= a[i].
   define p1(n) = p(n) / (sum(p(j), j=a[i]...a[20])), and p1(n)=0 for n < a[i].

Step 2.

   let i0 = argmin |p0(a[i0]) - 0.5|
   let i1 = argmin |p1(a[i1]) - 0.5|

等等...

当我们完成时，我们最终得到：

i, i0, i1, i00, i01, i10, i11, etc.

这些 i 中的每一个都为我们提供了比较位置。

所以现在我们的算法如下：

让 u = 输入数字。

if (u < a[i]) {
   if (u < a[i0]) {
      if (u < a[i00]) {
      } else {
      }
   } else {
      if (u < a[i01]) {
      } else {
      }
   }
} else {
   similarly...
}

所以我定义了一棵树，而 if 语句正在遍历树。我们也可以把它放到一个循环中，但是用一堆 if 来说明会更容易。

例如，如果您知道您的数据均匀分布在 0 到 2^63 之间，并且您的 20 数字是

0,1,2,3,...19

然后

i      = 20  (notice that there is no i1)
i0     = 10
i00    = 5
i01    = 15
i000   = 3
i001   = 7
i010   = 13
i011   = 17
i0000  = 2     
i0001  = 4     
i0010  = 6     
i0011  = 9
i00110 = 8
i0100  = 12
i01000 = 11
i0110  = 16
i0111  = 19
i01110 = 18

好的，基本上，比较如下：

if (u < a[20]) {
  if (u < a[10]) {
     if (u < a[5]) {
     } else {
         ...
     }
  } else {
     ...
  }
} else {
  return 21
}

所以请注意，我不是在做二进制搜索！我首先检查终点。为什么？

它有 100*((2^63)-20)/(2^63)% 的机会大于 a[20]。这基本上是 99.999999999999999783159565502899% 的机会！

因此，对于具有上述属性的数据集，该算法的预期比较次数为 1！（这比日志日志更好：p）

请注意我在这里所做的是，我基本上使用较少的比较来查找更可能的数字，并使用更多的比较来查找不太可能的数字。例如，数字 18 需要 6 次比较（比二分查找多 1 次）；但是，数字 20 到 2^63 只需要 1 次比较。同样的原理也用于无损（熵）数据压缩——使用更少的比特来编码经常出现的代码字。

构建树是一个一次性的过程，您可以在 100 万次之后使用该树。

问题是......这个决策树什么时候变成二分搜索？作业练习！:p 答案很简单。这类似于您无法再压缩文件时。

好的，所以我没有把这个从我的背后拉出来......基础在这里：

http://en.wikipedia.org/wiki/Arithmetic_coding

于 2013-02-09T12:00:05.523 回答
1

您可以使用std::lower_bound和std::upper_bound执行二进制搜索。这些为您提供了迭代器，因此您可以使用它std::distance来获取索引。

于 2013-02-09T08:49:39.317 回答