为何sklearn的KNN算法使用不同距离度量时预测速度差异巨大？

• 硬件加速的针对性差异
  现代CPU/GPU的SIMD指令集（比如Intel AVX2）和主流BLAS库（MKL、OpenBLAS）对欧氏距离的核心计算——向量平方和做了极致优化，能一次性批量处理多个维度的计算，并行效率拉满。而曼哈顿距离需要计算每个维度差的绝对值再求和，绝对值操作在SIMD中的执行效率远低于平方，且几乎没有BLAS库为L1距离做专门优化，只能靠朴素循环，并行度上不去。

• KNN树结构的剪枝效率差异
  sklearn的KNN默认用KD-Tree或Ball-Tree查询。这两种树对L2距离有天然的剪枝优势：比如KD-Tree在选择分割维度、计算距离下界时，L2的数学性质能快速排除不可能成为近邻的节点，大幅减少需要遍历的分支。但L1距离的距离下界计算不够紧凑，树的剪枝效果几乎失效，查询时不得不遍历大量节点，甚至退化成暴力搜索，时间直接爆炸。

• 内存与指令流水线的影响
  欧氏距离的平方和操作内存访问模式连续，更容易被CPU缓存命中，且指令流水线能持续高效运行。而曼哈顿距离的绝对值操作会打断CPU的指令流水线，降低吞吐率；同时如果内部实现没适配最优内存布局，缓存命中率也会下降，进一步拖慢速度。

你说的“理论计算量相近”是对的，但实际性能差在工程实现的优化倾斜——sklearn优先对更常用的L2距离做了全链路优化，而L1距离的优化程度远远跟不上。

内容的提问来源于stack exchange，提问作者Zadig