查找附近值的二进制搜索
Binary search with looking nearby values
我正在尝试查找，是否有人按以下方式实现了二进制搜索 -
假设我们有一些元素的数组，放置在连续的内存中。
那么当你比较中间的元素时，接下来的几个元素应该已经在CPU缓存中了。比较应该已经免费了吧？
但是我找不到任何人这样做。
如果没有人这样做，可能是什么原因？
我认为你的建议很不错，虽然它比你最初想象的要稍微复杂一些。它仅适用于比较数据位于连续数组本身（而不是让数组保存指针）的情况。这在高级语言中不太常见。
从那里开始，它变得更加技术化。您打算使用 L1 缓存还是 L2 缓存？实际上，如果它在 L1 缓存中，它可能只是“免费”。您是要查询 CPU 架构来获取缓存行大小，还是要使用通用架构的规范？您的 OS 和体系结构是否允许您根据地址模数确定您在缓存行中的位置？ （我假设可以确定，但我不确定。）
您正在尝试比 O(log(n)) 更快。使用这种方法可以节省多少跳跃？如果您的下一个跳转位于同一缓存行中，则说明您通过迭代完成了更多工作。它仅在您的目标在您的缓存行中但您的下一个跳转不在时有帮助。 L1 缓存行可能包含 8 个（8 字节）或 16 个（4 字节）值，如果我们平均位于缓存行的中间，则只有一半可用。
我认为在这一点上它变得依赖于数据。你能预测你的目标“接近”你当前的位置吗？最后，我的意思是在 16 个值以内？如此接近意味着您在 log2(16)=4 次近距离跳转内，并且很可能其中一些跳转在缓存中。它们可能都在 L2 缓存中。毕竟，我认为这不值得；你不会再快了。
经典二分查找可以认为是在元素上定义一个二叉树结构。例如，如果您的数组有 15 个元素，编号从 1 到 15，您可以从查看中间元素“8”开始，然后从那里向左或向右移动到元素“4”或“12”：
（来自 Brodal 等人，“通过小高度的二叉树缓存不经意的搜索树”，SODA'02，PDF preprint link）
您的提议实质上是在每个节点中添加更多元素，以便“8”元素也包含一些相邻元素，例如“9”、“10”、“11”。我不认为这之前已经被广泛研究过，但是已经研究了另一个非常相关的想法，即从二叉树（每个节点上有两个 children）到 B-ary 树（“B-tree”，每个节点上有 B children）。这是您在一个节点中有多个元素的地方，这些元素将结果数据分成许多不同的范围。
通过将搜索关键字与节点中的 B-1 个不同元素进行比较，您可以确定要递归到 B children 中的哪一个。
可以重新排列数组中的元素，这样就可以在不使用指针和多次内存分配的情况下实现这种搜索结构，因此它变得与在常规排序数组中进行二进制搜索一样space-efficient ，但在进行搜索时“跳跃”较少。在常规排序数组中，二分搜索大致执行 log_2(N) 次跳跃，而在 B-tree 中搜索仅执行 log_2(N) / log_2(B) = log_B(N)次跳跃，少了log_2(B)次！
Sergey Slotin 写了一篇博客 post，其中包含一个完整示例，说明如何实现隐式存储在数组中的静态 B-tree：https://algorithmica.org/en/b-tree
我正在尝试查找，是否有人按以下方式实现了二进制搜索 -
假设我们有一些元素的数组，放置在连续的内存中。
那么当你比较中间的元素时，接下来的几个元素应该已经在CPU缓存中了。比较应该已经免费了吧？
但是我找不到任何人这样做。
如果没有人这样做，可能是什么原因？
我认为你的建议很不错，虽然它比你最初想象的要稍微复杂一些。它仅适用于比较数据位于连续数组本身（而不是让数组保存指针）的情况。这在高级语言中不太常见。
从那里开始，它变得更加技术化。您打算使用 L1 缓存还是 L2 缓存？实际上，如果它在 L1 缓存中，它可能只是“免费”。您是要查询 CPU 架构来获取缓存行大小，还是要使用通用架构的规范？您的 OS 和体系结构是否允许您根据地址模数确定您在缓存行中的位置？ （我假设可以确定，但我不确定。）
您正在尝试比 O(log(n)) 更快。使用这种方法可以节省多少跳跃？如果您的下一个跳转位于同一缓存行中，则说明您通过迭代完成了更多工作。它仅在您的目标在您的缓存行中但您的下一个跳转不在时有帮助。 L1 缓存行可能包含 8 个（8 字节）或 16 个（4 字节）值，如果我们平均位于缓存行的中间，则只有一半可用。
我认为在这一点上它变得依赖于数据。你能预测你的目标“接近”你当前的位置吗？最后，我的意思是在 16 个值以内？如此接近意味着您在 log2(16)=4 次近距离跳转内，并且很可能其中一些跳转在缓存中。它们可能都在 L2 缓存中。毕竟，我认为这不值得；你不会再快了。
经典二分查找可以认为是在元素上定义一个二叉树结构。例如，如果您的数组有 15 个元素，编号从 1 到 15，您可以从查看中间元素“8”开始，然后从那里向左或向右移动到元素“4”或“12”：
（来自 Brodal 等人，“通过小高度的二叉树缓存不经意的搜索树”，SODA'02，PDF preprint link）
您的提议实质上是在每个节点中添加更多元素，以便“8”元素也包含一些相邻元素，例如“9”、“10”、“11”。我不认为这之前已经被广泛研究过，但是已经研究了另一个非常相关的想法，即从二叉树（每个节点上有两个 children）到 B-ary 树（“B-tree”，每个节点上有 B children）。这是您在一个节点中有多个元素的地方，这些元素将结果数据分成许多不同的范围。
通过将搜索关键字与节点中的 B-1 个不同元素进行比较，您可以确定要递归到 B children 中的哪一个。
可以重新排列数组中的元素，这样就可以在不使用指针和多次内存分配的情况下实现这种搜索结构，因此它变得与在常规排序数组中进行二进制搜索一样space-efficient ，但在进行搜索时“跳跃”较少。在常规排序数组中，二分搜索大致执行 log_2(N) 次跳跃，而在 B-tree 中搜索仅执行 log_2(N) / log_2(B) = log_B(N)次跳跃，少了log_2(B)次！
Sergey Slotin 写了一篇博客 post，其中包含一个完整示例，说明如何实现隐式存储在数组中的静态 B-tree：https://algorithmica.org/en/b-tree