18

二进制搜索对于均匀分布非常有效。列表中的每个成员都有相同的“命中”概率。这就是为什么你每次都尝试中心。

有没有一种有效的算法来解决不均匀分布？例如，遵循 1/x 分布的分布。

4

6 回答 6

10

二叉搜索和二叉树之间有很深的联系——二叉树基本上是一种“预先计算的”二叉搜索，其中切割点由树的结构决定，而不是在搜索运行时被选择。事实证明，处理每个键的概率“权重”有时是用二叉树完成的。

一个原因是因为它是一棵相当普通的二叉搜索树，但预先知道，并且知道查询概率。

Niklaus Wirth 在他的“算法和数据结构”一书中介绍了这一点，其中有几种变体（一种用于 Pascal，一种用于 Modula 2，一种用于 Oberon），其中至少一种可以从他的网站下载。

不过，二叉树并不总是二叉搜索树，二叉树的一种用途是派生Huffman 压缩码。

无论哪种方式，二叉树都是从叶子分开开始构建的，并且在每一步中，将两个最不可能的子树连接成一个更大的子树，直到只剩下一个子树。为了在每一步有效地挑选两个最不可能的子树，使用了优先级队列数据结构——也许是二叉堆。

一棵构建一次然后永不修改的二叉树可以有多种用途，但可以有效更新的二叉树甚至更有用。有一些重量平衡的二叉树数据结构，但我不熟悉它们。当心 - 术语“权重平衡”通常用于每个节点的权重始终为 1，但子树的权重是近似平衡的。其中一些可能适用于不同的节点权重，但我不确定。

无论如何，对于数组中的二进制搜索，问题在于可以使用任意概率分布，但效率低下。例如，您可以有一个运行总权重数组。对于二进制搜索的每次迭代，您都希望确定中途概率分布点，因此您确定该值，然后搜索 running-total-of-weights 数组。您获得了主要二分搜索的完美权重平衡的下一个选择，但您必须对运行的总数组进行完整的二分搜索才能做到这一点。

但是，如果您可以在不搜索已知概率分布的情况下确定加权中点，则该原理有效。原理是一样的 - 您需要概率分布的积分（替换运行的总数组），当您需要一个中点时，您可以选择它以获得积分的精确中心值。这更像是一个代数问题而不是编程问题。

像这样的加权二分搜索的一个问题是，最坏情况下的性能更差 - 通常是由常数因素决定的，但是如果分布足够倾斜，您最终可能会得到有效的线性搜索。如果您假设的分布是正确的，尽管偶尔会出现缓慢的搜索，但平均情况下的性能会有所提高，但是如果您的假设分布是错误的，那么当许多搜索是针对根据该分布不太可能出现的项目时，您可以为此付费。在二叉树形式中，“不太可能”的节点距离根的距离比它们在简单平衡（假设平坦概率分布）二叉树中的距离更远。

一个平坦的概率分布假设即使在完全错误的情况下也能很好地工作——最坏的情况是好的，而最好的和平均的情况必须至少按照定义那么好。离平坦分布越远，如果实际查询概率与您的假设大相径庭，情况就会越糟糕。

于 2013-06-01T13:36:24.350 回答
5

让我准确地说。你想要的二进制搜索是：

 Given array A which is sorted, but have non-uniform distribution
 Given left & right index L & R of search range
 Want to search for a value X in A

 To apply binary search, we want to find the index M in [L,R] 
 as the next position to look at.

 Where the value X should have equal chances to be in either range [L,M-1] or [M+1,R]

一般来说，你当然想选择你认为X值应该在A中的M。因为即使你错过了，总“机会”的一半也会被淘汰。

所以在我看来你对分发有一些期望。如果您能告诉我们“1/x 分布”到底是什么意思，那么也许这里有人可以帮助建立我对您的建议。

让我举一个有效的例子。

我将使用与@Leonid Volnitsky 类似的“1/x 分布”解释

这是生成输入数组的 Python 代码A

from random import uniform

# Generating input
a,b = 10,20
A = [ 1.0/uniform(a,b) for i in range(10) ]
A.sort()

# example input (rounded)
# A = [0.0513, 0.0552, 0.0562, 0.0574, 0.0576, 0.0602, 0.0616, 0.0721, 0.0728, 0.0880]

假设要搜索的值为：

X = 0.0553

那么X的估计指数为：

= total number of items * cummulative probability distribution up to X
= length(A) * P(x <= X)

那么如何计算P(x <= X)呢？这种情况很简单。我们将 X 反转回 [a,b] 之间的值，我们将调用它

X' = 1/X ~ 18

因此

P(x <= X) = (b-X')/(b-a)
          = (20-18)/(20-10)
          = 2/10

所以 X 的期望位置是：

10*(2/10) = 2

嗯，这非常准确！

要重复预测 X 在 A 的每个给定部分中的位置的过程，需要做更多的工作。但我希望这足以说明我的想法。

我知道， 如果您只需一步就可以接近答案，那么这可能不再像是二分搜索了。但是承认，如果你知道输入数组的分布，这是你可以做的。

于 2013-06-01T12:46:08.767 回答
3

二进制搜索的目的是，对于已排序的数组，每次将数组减半时，您都会最小化最坏情况，例如，您可以执行的最差检查次数是 log2(entries)。如果您进行某种“不均匀”的二分搜索，将数组分成更小和更大的一半，如果元素始终位于较大的一半中，您可能会遇到最坏的情况。所以，我认为无论预期分布如何，二进制搜索仍然是最好的算法，因为它具有最好的最坏情况行为。

于 2013-06-01T12:51:35.987 回答
3

例如，您有一个条目向量[x1, x2, ..., xN]，并且您知道查询的分布是在1/x您拥有的向量上以概率给出的。这意味着您的查询将使用该分布进行，即，在每次咨询时，您将xN获得更高概率的元素。

这会导致您的二叉搜索树在考虑标签的情况下保持平衡，但不会对搜索执行任何策略。这个策略的一个可能的改变是放宽平衡二叉搜索树的约束——在父节点的左边更小，在右边更大——并且实际上选择父节点作为具有更高概率的节点，并且他们的子节点作为两个最可能的元素。

请注意，这不是二叉搜索树，因为您不是在每一步都将搜索空间除以二，而是相对于搜索模式分布的重新平衡树。这意味着您在最坏的情况下搜索可能会达到O(N). 例如，有v = [10, 20, 30, 40, 50, 60]：

        30
      /    \
    20      50
   /       /  \
 10       40   60

可以使用您的功能重新排序或重新平衡f(x) = 1 / x：

f([10, 20, 30, 40, 50, 60]) = [0.100, 0.050, 0.033, 0.025, 0.020, 0.016]
sort(v, f(v)) = [10, 20, 30, 40, 50, 60]

进入一个新的搜索树，看起来像：

        10  -------------> the most probable of being taken
      /    \               leaving v = [[20, 30], [40, 50, 60]]
    20      30  ---------> the most probable of being taken
           /  \            leaving v = [[40, 50], [60]]
          40   50 -------> the most probable of being taken
              /            leaving v = [[60]]
             60

如果您搜索10，您只需要一个比较，但如果您正在寻找60，您将执行O(N)比较，这不将其限定为二分搜索。正如@Steve314 所指出的，离完全平衡的树越远，搜索的最坏情况就越糟糕。

于 2013-06-01T13:26:17.623 回答
2

我将从您的描述中假设：

  • X是均匀分布的
  • Y=1/X是您要搜索的数据，它存储在排序表中
  • 给定值y，您需要在上表中对其进行二分查找

二分搜索通常使用范围中心的值（中位数）。对于均匀分布，可以通过大致了解表中我们需要查找搜索值的位置来加快搜索速度。

例如，如果我们在[0,1]范围内有均匀分布的值并且查询是 for 0.25，那么最好不要查看范围的中心，而是查看范围的第一季度。

要对1/X数据使用相同的技术，请在表中存储不是Y而是逆1/Y。不是搜索y而是搜索反值1/y。

于 2013-06-01T13:09:25.443 回答
1

在预期条件下，未加权二分搜索甚至对于均匀分布的键都不是最佳的，但在最坏的情况下它是最佳的。

比例加权二分搜索（我已经使用了几十年）可以满足您对统一数据的要求，并通过对其他分布应用隐式或显式变换。排序的哈希表是密切相关的（我已经知道了几十年，但从来没有尝试过）。

在这个讨论中，我将假设数据是从 1..N 中统一选择的，并且在一个大小为 N 的数组中，该数组由 1..N 索引。如果它有不同的解决方案，例如值与 1/index 成正比的 Zipfian 分布，您可以应用逆函数来展平分布，或者 Fisher 变换通常会有所帮助（参见 Wikipedia）。

最初您将 1..N 作为边界，但实际上您可能知道实际的 Min..Max。在任何情况下，我们都会假设我们当前正在搜索的索引范围 [L..R] 始终有一个闭合区间 [Min,Max]，最初是 O(N)。我们正在寻找关键 K 并想要索引 I 以便

[IR]/[K-Max]=[LI]/[Min-K]=[LR]/[Min-Max] 例如 I = [RL]/[Max-Min]*[Max-K] + L。

舍入以使较小的分区变得更大而不是更小（以帮助最坏的情况）。预期的绝对误差和均方根误差为 <√[RL]（基于 Poisson/Skellam 或随机游走模型 - 参见 Wikipedia）。因此，预期的步数为 O(loglogN)。

最坏的情况可以通过多种方式限制为 O(logN)。首先，我们可以决定我们认为可接受的常数，可能需要步骤 1。继续执行上述 loglogN 步骤，然后对任何此类 c 使用减半来实现这一点。

或者，我们可以修改对数的标准底 b=B=2，使 b>2。假设我们取 b=8，那么实际上是 c~b/B。然后我们可以修改上面的舍入，以便在第 k 步，最大的分区最多只能是 N*b^-k。即，如果我们从每一步的考虑中消除 1/b，从而导致最坏情况 b/2 lgN，则跟踪预期的大小。然而，这将使我们的预期情况回到 O(log N)，因为我们每次只能将小分区减少 1/b。在应用受限舍入之前，我们可以通过对 loglogN 步骤使用小分区的简单向上舍入来恢复 O(loglog N) 期望。这是合适的，因为在预期是特定值局部的突发内，分布近似均匀（即对于任何平滑分布函数，例如在这种情况下 Skellam，

至于排序的哈希，我想我几十年前在 Knuth 上读过这个，但找不到参考。该技术涉及推送而不是探测 - （可能是加权二进制）搜索以找到正确的位置或间隙，然后根据需要推到一边以腾出空间，并且散列函数必须尊重排序。这种推动可以环绕，因此需要第二次通过表格才能将它们全部拾起 - 跟踪 Min 和 Max 及其索引很有用（以获得从一个开始的正向或反向排序列表并循环跟踪到另一个；然后它们也可以用来代替 1 和 N 作为上述搜索的初始括号；否则 1 和 N 可以用作代理项）。

如果负载因子 alpha 接近 1，则预期 O(√N) 项的插入预期为 O(√N)，平均而言仍摊销为 O(1)。预计此成本将随 alpha 呈指数下降 - 我相信（在泊松假设下）μ ~ σ ~ √[Nexp(α)]。

上述按比例加权的二分搜索可用于改进初始探测。

于 2015-11-22T01:35:08.950 回答