Python计算Moran's I时如何加速百万级点集邻域查找操作

当前实现采用暴力逐点遍历计算全量点对距离，时间复杂度为O(N²)，N=200万时总计算量达4万亿次，属于复杂度层面的本质问题，小范围代码调优无法解决性能瓶颈，必须替换为基于空间索引的固定半径近邻搜索方案。

3维坐标场景下优先选择C实现的KD树做批量固定半径邻域查询，整体时间复杂度可降至O(NlogN)，200万点规模在普通消费级CPU上数分钟即可跑完。
同时配合numpy向量化操作消除Python层循环开销：

• 距离判断直接使用平方值与阈值平方比较，省略sqrt开根号的冗余计算
• 所有统计值累加全部采用向量化逻辑，避免列表推导、逐元素循环的性能损耗

参考代码如下，计算逻辑与原实现完全对齐，结果无偏差：

import numpy as np
from scipy.spatial import cKDTree

dist_thresh = 1.99
z = x - x.mean()
n = len(coords)
B = (z ** 2).sum()

# 构建空间索引，调用全部CPU核心并行查询所有邻接点对
tree = cKDTree(coords)
# query_pairs返回无向唯一邻接对(i,j)，满足i<j、两点距离小于阈值
pairs = tree.query_pairs(r=dist_thresh, workers=-1)

# 对齐原逻辑的双向计数规则
S_0 = 2 * len(pairs)
i_arr = np.fromiter((p[0] for p in pairs), dtype=np.int64, count=len(pairs))
j_arr = np.fromiter((p[1] for p in pairs), dtype=np.int64, count=len(pairs))
A = 2 * (z[i_arr] * z[j_arr]).sum()

I = (n / S_0) * (A / B)

• 若点集规模进一步扩大到千万级，或坐标维度更高，可替换为基于近邻下降算法的近似近邻搜索库，内存占用更低、查询速度更快
• 若构建KD树时内存不足，可对点集做规则网格分块，仅查询相邻块内的点对，大幅降低内存峰值
• 禁止逐点调用单例查询接口，必须使用批量查询方法，避免频繁的函数调用、内存拷贝开销

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