改进元组距离计算算法以提高时间效率

Question

我有一个算法计算每个点p(我的元组中表示的坐标值)与元组列表中的每个其他元组的距离.

点数列表:

centerList = [(54, 2991),
            (1717, 2989),
            (1683, 2991),
            (1604, 2991),
            (114, 2991),
            (919,222),
            (930,233)]

距离functoin:

def getDistance(p0, p1):
    return math.sqrt((p0[0] - p1[0])**2 + (p0[1] - p1[1])**2)

用于计算p元组列表中每个其他点的距离的算法.

i = 0
distanceList = []
for p in range(len(centerList)):
    while i < len(centerList):
        print centerList[p], centerList[i], getDistance(centerList[p], centerList[i])
        distance = getDistance(centerList[p], centerList[i])
        if distance < 20:
            distanceList.append(distance)
        i += 1
    i = p + 2

我当前的算法以不冗余的方式递增,但在当前状态下,它对于实际应用来说太粗暴.我的问题在于我的实际centerList包含数千个元组.

可以做些什么来提高这种元组比较算法的时间效率？

Answer 1

你可以结合sklearn.metrics.euclidean_distances使用numpy布尔索引进行计算:

>>> from sklearn.metrics import euclidean_distances
>>> import numpy as np
>>> centerList = np.array(centerList)
>>> distances = euclidean_distances(centerList)
>>> distances[distances<20]
array([  0.        ,   0.        ,   0.        ,   0.        ,
         0.        ,   0.        ,  15.55634919,  15.55634919,   0.        ])

距离的计算使用在高速C中开发的numpy矩阵代数.文档还强调了基础数学技术的效率:

出于效率原因,一对行向量x和y之间的欧氏距离计算如下:

dist(x, y) = sqrt(dot(x, x) - 2 * dot(x, y) + dot(y, y))

与其他计算距离的方法相比,这种公式有两个优点.首先,它在处理稀疏数据时具有计算效率.其次,如果一个参数变化但另一个参数保持不变,则可以预先计算点(x,x)和/或点(y,y).