python – 在2D中找到点组之间的最小距离(快速且不太耗费内存)

概述我在2D A和B中有两组点,我需要找到A中每个点的最小距离,到B中的一点.到目前为止,我一直在使用SciPy的 cdist,代码如下 import numpy as npfrom scipy.spatial.distance import cdistdef ABdist(A, B): # Distance to all points in B, for each point in A 我在2D A和B中有两组点,我需要找到A中每个点的最小距离,到B中的一点.到目前为止,我一直在使用SciPy的 cdist,代码如下

import numpy as npfrom scipy.spatial.distance import cdistdef ABdist(A,B):    # distance to all points in B,for each point in A.    dist = cdist(A,B,'euclIDean')    # Indexes to minimum distances.    min_dist_IDx = np.argmin(dist,axis=1)    # Store only the minimum distances for each point in A,to a point in B.    min_dists = [dist[i][md_IDx] for i,md_IDx in enumerate(min_dist_IDx)]    return min_dist_IDx,min_distsN = 10000A = np.random.uniform(0.,5000.,(N,2))B = np.random.uniform(0.,2))min_dist_IDx,min_dists = ABdist(A,B)

这适用于N的小值.但是现在这些集的长度从N = 10000增加到N = 35000并且我遇到了

dm = np.zeros((mA,mB),dtype=np.double)MemoryError

我知道我可以用一个for循环替换cdist,它只保留A中每个点到B中每个点的最小距离(和索引),因为这就是我所需要的.我不需要完整的AxB距离矩阵.但我一直在使用cdist,因为它很快.

有没有办法用一个(差不多？)快的实现来替换cdist,但这不会占用那么多内存？

解决方法 最好的方法是使用专门为最近邻搜索设计的数据结构,例如 k-d tree.例如,SciPy的 cKDTree允许您以这种方式解决问题：

from scipy.spatial import cKDTreemin_dists,min_dist_IDx = cKDTree(B).query(A,1)

在计算和存储器使用方面,结果比基于广播的任何方法更有效.

例如,即使有1,000,000个点,计算也不会耗尽内存,并且在我的笔记本电脑上只需几秒钟：

N = 1000000A = np.random.uniform(0.,2))%timeit cKDTree(B).query(A,1)# 3.25 s ± 17.9 ms per loop (mean ± std. dev. of 7 runs,1 loop each)

总结

以上是内存溢出为你收集整理的python – 在2D中找到点组之间的最小距离(快速且不太耗费内存)全部内容，希望文章能够帮你解决python – 在2D中找到点组之间的最小距离(快速且不太耗费内存)所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。