Julia中快速计算两组3D点集最小距离的优化问询

原代码通过pairwise生成完整的5000×5000距离矩阵后取最小值，这种方式会占用大量内存（约200MiB）且时间复杂度为O(n*m)（n、m为点集大小），可以从以下几个方向优化：

1. 避免生成全距离矩阵，逐点计算并跟踪最小值 #

直接对A中的每个点，遍历B计算距离并记录最小值，无需存储完整的距离矩阵，内存占用大幅降低：

using Distances

A = rand(5000, 3)
B = rand(5000, 3)

sq_dist = SqEuclidean()
mis = @time vec([minimum(evaluate(sq_dist, A[i,:], B[j,:]) for j in 1:size(B,1)) for i in 1:size(A,1)])

注：纯Julia循环的效率可以通过添加@inbounds和@fastmath进一步提升：

mis = Vector{Float64}(undef, size(A,1))
@time @inbounds @fastmath for i in 1:size(A,1)
    min_d = Inf
    ai = A[i,:]
    for j in 1:size(B,1)
        d = (ai[1]-B[j,1])^2 + (ai[2]-B[j,2])^2 + (ai[3]-B[j,3])^2
        if d < min_d
            min_d = d
        end
    end
    mis[i] = min_d
end

2. 利用平方欧氏距离的代数公式优化计算 #

平方欧氏距离可拆解为：||a-b||² = ||a||² + ||b||² - 2a·b，借助BLAS矩阵乘法加速点积计算，同时避免冗余运算：

using LinearAlgebra

A = rand(5000, 3)
B = rand(5000, 3)

norm_A_sq = sum(A.^2, dims=2)
norm_B_sq = sum(B.^2, dims=2)'
dot_AB = A * B'

# 逐行计算最小距离，无需存储完整距离矩阵
mis = @time vec(minimum(norm_A_sq .+ norm_B_sq .- 2 .* dot_AB, dims=2))

这种方法仍为O(n*m)复杂度，但BLAS优化的矩阵乘法比逐点计算更快，内存上仅需存储点积矩阵（与原方案相当，但计算效率更高）。

3. 使用空间索引库降低时间复杂度（最优方案） #

对于大规模点集，使用KDTree等空间索引结构可将时间复杂度降至O(n log m)，大幅提升速度并减少内存占用，推荐使用NearestNeighbors.jl：

using NearestNeighbors

A = rand(5000, 3)
B = rand(5000, 3)

# 构建KDTree（库要求点按列存储）
kdtree = KDTree(B')
# 查询每个A中点到B的最近邻平方距离
mis, _ = @time knn(kdtree, A', 1, true)  # true表示返回距离值
mis = vec(collect(Iterators.flatten(mis)))

该方案无需生成全距离矩阵，空间索引会快速缩小搜索范围，对于5000个点的规模，速度和内存占用会有数量级的提升。

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