DEBUG.WIKI
京东云;让 AI 进入真实业务;零售 · 物流 · 客服 · 硬件;查看方案 →
ZgoCloud:多地区部署,按需选节点;日本、美国、香港、德国
Evoxt;最高 6.0GHz CPU;高频云服务器 · 免费每周备份;查看配置 →

KDTree 半径查询遇大量相同距离崩溃,定位 simultaneous_sort 递归

KDTree 返回结果排序遇大量相同距离可能耗尽原生递归栈,可更新 introsort 修复版本并检查索引与距离的配对。

KDTree.query_radius(..., return_distance=True, sort_results=True) 对部分查询点正常,对另一点却直接使 Python 进程段错误退出。scikit-learn 1.8.0 的 Linux 案例中,原生回溯反复出现 simultaneous_sort;大量相同距离让内部排序进入很深的递归。

这条路径按距离排序,同时移动相应的邻居索引。旧快速排序对重复值的分割会严重失衡,可能出现二次时间复杂度和线性递归深度。Python 层没有抛出普通异常,因此调高 sys.setrecursionlimit() 不会修复这个 C 扩展排序栈。

区分查询计算与结果排序

保留原数据和同一个查询点,先比较是否仅开启 sort_results 才失败。确需回溯时可以用 Python 的故障处理入口运行原脚本:

python -X faulthandler original_query.py

日志中的函数名有诊断价值;单独一行 Segmentation fault 不足以确定根因。也不能因为 macOS 上没有崩溃,就断言输入或 Linux 环境一定错误:栈限制及构建差异会改变症状。

scikit-learn 1.9.0 包含对应排序修复,改用有递归深度预算、必要时退回堆排序的 introsort。更新实际执行查询的环境,并对原来失败的数据复验,不能只检查一个新建树能成功。

暂时把排序移到 NumPy

如果尚不能更新且业务必须返回有序距离,可关闭受影响的排序,再同步排列索引和距离:

import numpy as np

indices, distances = tree.query_radius(
    query, radius, return_distance=True, sort_results=False
)
ordered = []
for idx, dist in zip(indices, distances):
    order = np.argsort(dist, kind="stable")
    ordered.append((idx[order], dist[order]))

这里的 tree、query、radius 使用原调用的对象和参数。该绕法只避开返回结果的内部排序;如果无序查询也崩溃,要按新的回溯处理。返回索引和距离必须使用同一 order,不能只排距离后继续沿用旧索引。

验收除了不崩溃,还要检查距离非递减、每个索引对应的距离正确、邻居集合未变。用一组重复坐标加少量不同距离的点补充测试,能覆盖重复值和排列配对;小数据通过不代表已经重现或排除了原大数据栈溢出。

等距离邻居的顺序不一定具有业务意义。stable 保留的是无序查询返回的相对顺序,不承诺跨数据集、构建或平台得到相同的平局顺序。需要固定次序时,另外定义明确的二级排序键;不要扰动坐标或给距离加随机噪声来隐藏排序退化。