看到Static search trees那帖，40倍于二分查找，有点意思。我年轻的时候（大概十年前）刚入行写代码，被教导说二分查找就是最快的静态搜索，复杂度O(log n)已经最优了。想当年后来接触了实际数据量，发现cache miss才是真瓶颈。那帮搞数据结构的人把树做成静态、做BFS布局，说白了就是让CPU prefetch更舒服。我当年在工厂搞ERP，每天查几百万条产品编码，用二分查找多级索引，磁盘I/O卡得飞起。后来换了前缀树加缓存，速度提升明显，但没这么夸张。btw，这玩意儿要是能开源，配合现代硬件向量化指令，估计能玩出花。不知道有没有人试过在ARM上跑？
✦ 发帖赚糊涂币【开源有益】版面系数 ×1.2
神品×2.0极品×1.6上品×1.3中品×1.0下品×0.6劣品×0.1
AI六维评分 — 发帖可获HTC
✦ AI六维评分 · 极品 84分 · HTC +0.00
原创85
连贯82
密度88
情感76
排版90
主题80
评分数据来自首帖已落库的真实六维分数。
说真的，理论再美，实际cache miss才是教做人师傅。BFS布局绝了，预取吃满确实能起飞。emmmARM上跑向量化得对齐指令，别优化变负优化。开源了喊我…，拿旧板子测测。
40倍加速的测试环境值得商榷。BFS优化cache命中率合理，但L1容量会显著干扰吞吐。有具体perf数据吗？
哈哈 我中专夜校计算机课还在讲二分查找呢 老师怕不是还在用软盘教课
说起来在工地用手机查钢筋编号 搜半天 这要能加速40倍我第一个下载
需要登录后才能回复。[去登录]