慢欧氏距离

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 或用 ** .5 替换 sqrt，或者（可能是最好的) 将整个内容替换为 np.hypot。（如果您不知道如何使用 timeit——或者更好的是，IPython 并且它是 %timeit 魔法——现在是学习的好时机。）

但最终，这只会为您提供大约一个数量级的常数乘数加速。也许需要 15 分钟而不是 3 小时。很好，但是……为什么一开始就花了 3 个小时？您在这里所做的应该以秒为单位，甚至更短。这里显然有一些更大的错误，比如当你认为你只调用它一次时，你可能调用了这个函数 N**2 次。你真的需要修复那个部分。

当然这样做还是值得的。首先，逐元素操作比循环更简单、更易读，也更不容易出错。其次，即使你将整个程序缩短到 3.8 秒，你也会为 0.38 秒的数量级加速而感到高兴，对吧？

Answer 2

自己写 sqrt 计算器有其自身的风险，hypot 非常安全，可以抵抗上溢和下溢

x_y = np.array(trainingSet)
x = x_y[0]
y = x_y[1]
distances = np.hypot(
    np.subtract.outer(x, x),
    np.subtract.outer(y, y)
)

在速度方面它们是相同的

%%timeit
np.hypot(i, j)
# 1.29 µs ± 13.2 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

%%timeit
np.sqrt(i**2+j**2)
# 1.3 µs ± 9.87 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

下溢

i, j = 1e-200, 1e-200
np.sqrt(i**2+j**2)
# 0.0

溢出

i, j = 1e+200, 1e+200
np.sqrt(i**2+j**2)
# inf

无下溢

i, j = 1e-200, 1e-200
np.hypot(i, j)
# 1.414213562373095e-200

无溢出

i, j = 1e+200, 1e+200
np.hypot(i, j)
# 1.414213562373095e+200

慢欧氏距离

Slow Euclidean Distance

python

numpy

knn

下溢

溢出

无下溢

无溢出