按年被提到
20152015 · 4 次2026
算法与数据结构›经典算法与数据结构·arXiv:1509.05053 · cs.DS

Array Layouts for Comparison-Based Searching

基于比较的搜索中的数组布局
Paul-Virak Khuong, Pat Morin · 2015

比较排序数组、Eytzinger、B 树和 vEB 布局下的搜索速度

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 13 人首次 2015-10-15 · 最近 2026-07-18发表于 ACM Journal of Experimental Algorithmics
13不同的人
13活跃月份
16讨论串
31被引(OpenAlex)

论文比较了在内存数组中支持「查找不小于 x 的最小值」的几种布局与搜索算法:有序数组加二分搜索、Eytzinger(BFS)布局、隐式 B 树布局和 van Emde Boas 布局。经过在多种现代硬件上的大量测试和调优,结论是:n 较小时,有序数组加好的二分搜索最佳;n 较大时,Eytzinger 布局通常最快,与 Brodal 等人此前的实验结论相反。最快的 C++ 实现用条件移动避免分支预测失败,并用预取减少缓存延迟。

HN 为什么提它

HN 上的人在讨论二分搜索的分支预测与缓存行为时反复引用它,说明内存延迟而非访问次数才是代价,并用来比较无分支实现与缓存布局的效果。

实证研究难度 3 / 5约 60 分钟经得起时间
读之前最好知道
1二分搜索与堆的数组表示
2CPU 缓存与预取(prefetching)
3分支预测与条件移动(cmov)
4缓存无关算法(cache-oblivious algorithms)

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
推荐nkurz · 2015-10

“Just came across a good paper that discusses these issues:”

推荐这篇刚看到的论文,讨论这类问题
Assist threads原评论 ↗
推荐nkurz · 2015-10

“I think the summary from this recent paper is spot on:”

认为这篇近期论文的总结一针见血
Memory Is Holding Up the Moore's Law Progression of Processing Power (2014)原评论 ↗
推荐jsnell · 2017-06

“Have a look at Array Layouts for Comparison-Based Searching from pkhuong. They discuss this issue and other variants that paper.”

推荐 pkhuong 的这篇论文,讨论了这个问题及其变体
SIMD / GPU Friendly Branchless Binary Search原评论 ↗
引用Arcuru · 2020-05

“Reminds me of this paper on binary search, which also shows a speed up using branch-free comparisons.”

联想到这篇论文同样用无分支比较加速二分查找
Lomuto's Comeback原评论 ↗
引用pubby · 2020-07

“The more recent results (by the same author) is this paper:”

指出同一作者更新的成果是这篇论文
Binary Search: A new implementation that is up to 25% faster原评论 ↗
引用ot · 2022-02

“The best results I knew of for static ordered search [1] were from the 2015 Khuong-Morin paper [2]”

指出静态有序搜索已知的最佳结果来自 Khuong-Morin 这篇 2015 年论文
Static B-Trees: A data structure for faster binary search原评论 ↗
看全部 8 条 →
引用pkhuong · 2024-11

“can be restructured with a conditional `first += half` and instead `length -= half` (see, e.g., Listing 2 in Array Layouts for Comparison-Based Searching).”

指出论文 Listing 2 给出了无分支二分查找的写法
Fastest Branchless Binary Search原评论 ↗
引用mananaysiempre · 2026-07

“but the constants are bad enough to make it impractical[1,2].”

引用它说明 cache-oblivious 布局的常数大到不实用
Static search trees: 40x faster than binary search (2024)原评论 ↗
被提交为 story · 8 次