硬件并行加速数组索引 | AI生成和翻译
为什么索引比二分查找更快？
这篇由王垠于2013年撰写的博客文章深入探讨了直接数组索引（如arr[i]）为何是常数时间O(1)，而在有序数组上进行二分查找需要O(log n)时间的根本原因。作者通过简单的电路类比从硬件层面进行剖析，揭示索引并非“魔法”——它只是内置于计算机寻址系统中的大规模并行二分查找。
核心解析
- 核心思想：数组索引使用寻址电路直接从地址（如索引）选择内存位置。以4个内存位置（W, X, Y, Z）和2位地址（位A和B）的微型示例说明：
- 每个地址位就像二分查找的一个步骤，将可能的选择范围减半
- 位A决定两组选择：{W, X} 或 {Y, Z}
- 位B决定另一组分划：{W, Y} 或 {X, Z}
- 这些位并非顺序运行——它们通过与门和导线并行运作，结合信号并精确激活一个输出（例如A=0, B=1 → 选择W）
这模拟了二分查找的2个步骤（log₂(4)=2），但在单个硬件“时钟周期”内完成，因为所有操作都是同步进行的。
-
规模扩展：对于完整的n位地址（可处理2ⁿ个元素），该电路并行执行所有log₂(n)个二分查找步骤。这就是为什么它是O(1)：硬件瞬时完成“查找”，无需软件中的循环或比较操作。
- 可视化辅助：文章附有包含反相器、导线和与门的电路图，展示信号流向。虽无代码片段，但属于概念性图示——可将其视为将二进制地址转换为独热选择的解码器。
重要启示
王垠指出这揭示了底层硬件优化如何让高层操作变得轻松自如。二分查找的“缓慢”仅因其在软件中顺序模拟了这个电路，而CPU的实际内存访问采用的是并行版本。
这篇短小精悍的深度解析，非常适合那些渴望超越大O表示法去探索计算机科学本质的读者。