慢欧几里德距离

Question

我用下面的python代码计算欧几里德距离:

def getNeighbors(trainingSet, testInstance, k, labels):
    distances = []
    for x in range(len(trainingSet)):
        dist = math.sqrt(((testInstance[0] - trainingSet[x][0]) ** 2) +    ((testInstance[1] - trainingSet[x][1]) ** 2))
        distances.append([dist, labels[x]])
    distances = np.array(distances)   
    return distances

为了计算给定点与其他10个点的距离,这很好.但是当我用18563个其他点计算一个点的距离时,计算机会被挂起并且在3小时左右没有响应.

如何更快地计算 18563 点？

Answer 1

你可以通过首先转换为NumPy然后使用向量操作来加速它,而不是在循环中完成工作,然后转换为NumPy.像这样的东西:

trainingArray = np.array(trainingSet)
distances = ((testInstance[0] - trainingArray[:, 0]) ** 2 +
             (testInstance[1] - trainingArray[:, 1]) ** 2).sqrt()

(这显然是未经测试的,因为没有足够的上下文来知道我必须猜测的那些变量实际上是什么,但它会接近那个.)

还有其他一些事情可以用来挤出一些额外的% - 替换** 2自我乘法或sqrt用** .5,或(可能是最好的)替换整个事物np.hypot.(如果你不知道如何使用timeit-or,甚至更好,IPython和%timeit魔术 - 现在是学习的好时机.)

但最终,这只会给你一个大约一个数量级的常数倍增速度.也许需要15分钟而不是3个小时.那很好,但是......为什么一开始需要3个小时？你在这里做的事情应该是几秒钟,甚至更少.这里显然有一些更大的错误,比如当你认为你只召唤一次时,你可能会将这个功能调用N**2次.而你真的需要解决这个问题.

当然,这仍然值得这样做.首先,逐元素操作比循环更简单,更易读,更难以出错.其次,即使你把整个程序减少到3.8秒,你也会很高兴加速到0.38秒,对吗？