Eytzinger二进制搜索

本教程松散地基于Paul-Virak Khuong和Pat Morin为比较的搜索阵列布局的46页纸张，并描述了通过在缓存友好中重新排列排序阵列的元素来执行有效二进制搜索的一种特定方式方法。

我们简要介绍处理器架构中的相关概念;如果您想更深，我们建议您阅读原始2015纸，以及这些文章：

我们的简约实现仅限〜15行代码，同时提供4-5倍的Speedup over std :: dight_bound。精确加速度在可用的内存带宽上取决于很多（请参阅下面的注释）。

如果您现在正在写一场比赛，请卡在二进制搜索是一个瓶颈的问题上，突然记住了这篇文章，直接跳转到“完成”，它是可编译和复制的粘贴。

以下是在排序阵列中搜索不小于\（x \）的第一个元素的标准方法：

此（或任何）算法的运行时间不仅仅是其所有算术运算的“成本”，而且，这一成本加上等待数据从内存中获取的时间。因此，根据算法和问题限制，它可以是CPU绑定或内存绑定的，这意味着运行时间由其组件之一主导。

如果阵列足够大 - 通常在其停止拟合缓存中的点围绕缓存并取得更大速度 - 二进制搜索的运行时间因内存提取而占主导地位。

要了解一个想法，以下代码仅〜5％=（n \约10 ^ 6 \）：

现实更复杂，即G。主内存具有分页和HDD实际上是具有奇怪的访问模式的旋转物理的东西，但我们坚持这个类比并向它介绍一些重要的实体：

缓存层次结构是一种内存架构，其使用基于变化的访问速度来缓存数据的内存存储层次结构。相邻的缓存层通常大小不同，倍率为8到10，延迟倍率为3到5.大多数现代CPU具有3层高速缓存（名为L1，L2和L3，从最快/最小/最慢/最大）最大的是几兆字节大。

缓存行是CPU和主存储器之间的数据传输单位。 PC的缓存行最有可能是64个字节，这意味着主内存被分成64个字节的块，并且只要您请求字节，您也将获取其缓存行邻居，无论您是否想要它。获取缓存线就像抓取6包。

驱逐政策是决定将哪些数据保留在缓存中的方法。在CPU中，它由硬件控制，而不是软件。为简单起见，程序员可以假设使用最少使用最少使用的（LRU）策略，这只是逐步逐步用于最长时间的项目。这就像偏好的啤酒一样，以后的到期日期。

带宽是可以读取或存储数据的速率。出于设计算法的目的，一个更重要的特征是带宽 - 延迟产品，基本上讲述了在没有排队的情况下等待第一个的同时可以请求的高速缓存行。大多数系统约为5或更多。这就像让您可以异步为贝勒发送的朋友。

时间位置是一种访问模式，其中如果在一个点请求特定项目时，则可能在不久的将来再次请求相同的位置。这就像一遍又一遍地取出相同类型的啤酒。

空间局部是一种访问模式，其中如果要求存储器位置，则可能在不久的将来再次请求附近的存储器位置。这就像在同一架子上储存你喜欢的啤酒。

通过排序阵列的二进制搜索的主要问题是其存储器访问模式既不临时也不是间接本地。例如，元素\（\ lfloor \ frac n 2 \ rfloor \）经常访问（每个搜索）和元素\（\ lfloor \ frac n 2 \ rfloor + 1 \）不是，而他们可能占据相同缓存行。通常，只有前3-5读数是临时本地，只有最后3-4读数是完整的本地本地，其余的只是随机内存访问。

我们可以通过以更加缓存的方式枚举和释放数组元素来克服此功能。我们使用的作用实际上是半千禧年的历史，你已经知道了它。

MichaëlEytzinger是一个16世纪的奥地利贵族，以他的工作在族裔的工作中，特别是为一个名为Ahnentafel的祖先的系统（德语为“祖先桌”）。

祖先回到了很大问题，但是写下数据很昂贵。 Ahnentafel允许通过绘图图浪费额外的空间，允许在不浪费额外的空间的情况下展示一个人的家谱。

它列出了一个人以固定的上升顺序的直接祖先。首先，他们自己被列为1号，然后，递归地，对于编号的每个人，他们的父亲被列为\（2k \）和他们的母亲作为\（（2k + 1）\）。

除了紧凑，它有一些很好的属性，就像所有偶数人都是男性，所有奇数（可能与1分开）是女性。

人们还可以找到特定祖先的数量，只知道他们的后代的性格。例如，彼得伟大的血统是保罗我→彼得III→Anna Petrovna→彼得大伟大，所以他的号码应该是\（（（1 \ times 2）\ times 2 + 1）\ times 2 = 10 \）。

在计算机科学中，此枚举已被广泛用于隐式（即，无指针）实现堆，段树和其他二进制树结构，而不是将其存储在底层数组项的名称中。

您可以立即了解其时间位置如何更好（实际上，理论上最佳），因为靠近根的元素更接近阵列的开头，因此更有可能从缓存中获取。

它需要两个索引\（i \）和\（k \） - 原始阵列中的一个，一个在构造 - 且递归地到两个分支，直到达到叶节点，这可以通过断言\（k \ Leq n \）作为Eytzinger阵列应该具有相同数量的物品。

尽管存在递归，但实际上这实际上是一个非常快的实现，因为所有内存读数都是顺序的。

请注意，第一个元素未填充，整个阵列本质上为1移位。这实际上将成为一个巨大的性能助推器。

我们现在可以仅使用指数下降这个数组：我们刚刚从\（k = 1 \）开始，如果我们需要左右，则执行\（k：= 2k \），如果我们，\（k：= 2k + 1 \）需要走向。我们甚至不需要存储和重新计算二进制搜索边界。

当我们需要恢复生成元素的索引时，才会出现唯一的问题，因为\（k \）可能最终未指向叶节点。这是一个如何发生的例子：

在这里，我们查询\（[1，...，8] \）的阵列，以获取\（x = 4 \）的下限。我们将其与\（4 \），\（2 \）和\（5 \）进行比较，然后左右转到右侧，并以\（k = 11 \）结束，甚至不是有效的数组索引。

注意，除非答案是数组的最后一个元素，否则我们将\（x \）与它相比在某个时候，并且在我们了解到它不小于\（x \）后，我们开始比较\（x \ ）针对左侧的元素，所有这些比较将评估真实（即导致右侧）。因此，要恢复所得元素的解决方案是取消一些右转。

这可以通过观察右转旋转以\（k \）为1位的二进制符号记录，因此我们只需要找到二进制符号中的尾随数量和右转 - 按照该金额换档\（k \）。

为此，我们可以在大多数系统上颠倒（〜x）并呼叫“查找第一个设置”指令。在GCC中，相应的内置是__builtin_ffs。

请注意，如果二进制搜索返回任何结果（即，所有元素少于\（x \），则右转，所有元素均为右转，并且所有转弯都会被取消）。在这种情况下，您可以在B的第一个元素中放置特殊标志。

这已经比std :: dight_bound快2-3倍，但我们不会停止那里并应用一系列小的增量改进。

编译的程序指令也从主内存存储和加载，就像正常数据一样。它们在通过类似机制执行期间获取它们，并且它们具有单独的指令缓存。实际上，在大型应用程序中，您有时可以删除字面上未使用的代码的块，并且由于更好的指令缓存命中率，程序可能会运行得更快，但这是另一个文章的主题。

为避免在此处的内存延迟引起的性能点击，CPU提前加载20-ISH指令，但要执行此操作，因此需要提前了解哪些指令。如果程序有条件执行（if-s，while-s，for-s），则无法选中猜测。

分支错误规定（猜测“错误”分支的“IF”）成本约为10-20个周期。部分否定此惩罚，开发了硬件分支预测因子。这些是复杂的ad-hoc系统，使用统计方法 - 有些甚至使用简单的神经网络 - 以更准确的猜测。

在二进制搜索的情况下，如果我们的所有数据都是随机的，则分支预测根本没有帮助，仅仅因为它不能：所有比较都是50-50。这就是为什么我们需要摆脱if-s并将我们的主循环重写为以下方式：

编译器不喜欢CPU在等待内存提取时闲置。有时它可能需要猜测哪个缓存行将很快需要，并提前获取它（回想一下，带宽 - 延迟产品通常大于1）。

这适用于简单的访问模式，例如在越来越多或减少的顺序中迭代阵列，但对于类似于我们在这里的东西，它不会表现良好。

正如我们更多地了解我们的问题，而不是编译器所做的那样，我们可以明确地告诉它预取我们需要的缓存行。这是通过__builtin_prefetch在gcc中完成的：

这里，block_size等于16，正是覆盖高速缓存行所需的界面是多少。当我们在b + k * block_size引用缓存行时，我们引用\（k）的大孙子（block_size = \（2 \ times 2 \ times 2 \ times 2 \）或4左转）他的一层中的一些邻居（回想一下，同一级别的索引只是连续数字）。

这样做的一切都是有很大的机会，我们将预取一个我们将稍后使用的元素（（i + 4）\） - 迭代。什么机会，究竟是什么？嗯，事实证明，每次迭代都是恒定的。

请注意，对于树中的每个图层，除了第一个4且可能是最后一个，该层中的节点的数量可被16个，块大小可分开。这意味着每次迭代上的覆盖节点的分数仅取决于阵列关于其高速缓存行的第一偏移的位置。但更重要的是，可以让所有的\（k \）的祖孙被同样的缓存线覆盖。

实现这一目标的方法是将阵列的第一个元素放置到高速缓存行的第一位置（0索引），或者在高速缓存行的开头上放置数组本身，因为它是第一（即B [0] ）元素通过设计空白。这样的方式，前4个层的下一个\（1 + 2 + 4 + 8 = 15 \）元素将占据缓存行的其余部分，并且阵列的其余部分是在共享a的漂亮16元节点的漂亮16元块中anijigned。爷爷。

我们只需要询问内存管理器在缓存行的开头上分配我们的数组（默认情况下，它将在任何地方分配阵列），就是这样。为此，我们可以使用alplats说明符：

就是这个。现在，我们的算法在时间内不断预取4层/高速缓存行，这是由我们RAM的带宽覆盖的。这样，有效延迟减少了4倍，我们基本上交易带宽以实现延迟。

当\（n \）是2或靠近它的功率时，它适用最佳，因为分支预测器将难以弄定展开\（（\ log n）\） - th周期。

其性能因缓存大小和阵列长而异，但即使在较小的阵列（＆lt; 1mb）上，也可以保持＆gt; 3x。

预处理并不昂贵。射击与数组大小相同数量的查询成本的1％左右。

现代硬件不会为预取不属于您的缓存行而惩罚您，尽管这可能是旧CPU的问题，这可以通过简单的IF语句来解决。

出于某种原因，基本的二进制搜索实现（本文中的第一个代码块）已经比STD :: Sort快20％〜20％。

B树基本上是\（（k + 1）\） - ary树，意味着它们存储每个节点中的\（k \）元素，并在\（（k + 1）\）之间选择可能的分支而不是2。

它们广泛用于数据库中的索引，尤其是那些在磁盘上运行的人，因为如果\（k \）很大，这允许大的顺序内存访问在减少树的高度时。

为了执行静态二进制搜索，可以以隐式方式实现B树，i。 e。在没有实际存储任何指针并仅消费\（O（1）\）附加内存，并且可以等于高速缓存行大小，使得每个节点请求精确地提取一个高速缓存行。

结果，它们具有相同的生长速率，但似乎更大的计算持续的恒定。 虽然后者是可解释的（我们的循环只有5个指示;不能超过那个），以前是令人惊讶的。 如果计算无关紧要，Eytzinger二进制搜索应该更快地\（4 \）倍，因为它平均要求它们〜4倍。 B树使\（\ frac {\ log_ {17} n} {\ log_2 n} = \ frac {\ log n} {\ log 17} \ frac {\ log 2} {\ log n} = \ frac {\ log 2} {\ log 17} \约0.245 \）存储器访问每个二进制搜索请求，i。 e。 它请求〜4倍的缓存行才能获取 请注意，此方法虽然适用于单线程世界，但不太可能进入数据库和繁重的多线程应用程序，因为它牺牲了带宽以实现低延迟。