NumPy 2.5 让 np.searchsorted 最快提速 25 倍
来源：blog.scientific-python.org — 2026-09-29
📋 概述
np.searchsorted 是 NumPy 的二分查找实现，被直方图统计与区间查询广泛使用。NumPy 2.4 的实现在 C 里对每个键独立跑一遍二分，每次比较都形成依赖链，大数组下访问还会跨缓存行，顺序实现常被内存访问拖住。作者的向量化思路是让所有查询同步推进：先维护 lo/hi 区间并只更新仍活跃的查询；再观察到二分不必为每个键独立终止，改成所有区间每次收缩同样步数后即可去掉活跃掩码，又快最多 2 倍；最后用"左边界 + 长度"表示区间，把每查询状态从 O(K) 压到输出之外的 O(1)。改动进入 NumPy 2.5，基准中最快提速 25 倍。
🔑 核心要点
- np.searchsorted 是 NumPy 的二分查找实现，也是 Python Array API 标准的一部分
- NumPy 2.4 为每个键单独二分，每次比较形成依赖链，大数组还跨缓存行访问
- 向量化第一步：所有查询同步推进，用活跃掩码只更新未收敛的查询
- 关键观察：所有区间每轮收缩同样步数，活跃掩码可以整个去掉，又快最多 2 倍
- 用"左边界 + 长度"表示区间，每查询状态从 O(K) 降到输出之外的 O(1)
- 优化已进入 NumPy 2.5，基准中最快 25 倍提速
💡 金句
重要的观察是：二分查找其实并不需要为每个键独立终止。
👍 0
👎 0
← 返回 Lobsters 首页