老师好，关于欧几里得距离计算，有没有什么更高效的计算方式？
来源：10-1 总结，算法思想，大家加油
qq__SuperAlpaca_0
2018-06-28
自己老师布置的一个题目：在100W个100维的向量中，取出与给定的100维的向量，欧几里得距离最小的前K个向量。
我把这个问题分为了2部分，一个是计算部分，一个是统计部分。统计部分用到了索引堆，很好用！但是在计算部分，我使用最普通的计算公式，太耗费时间(8s)。所以有没有关于欧几里得距离更高效的计算方式？感谢波波老师了。
long start = System.currentTimeMillis();
//100W行向量，这里用数组表示一个向量
for (int i = 1; i < Const.MATRIX_ROW; i++) {
//每一行与给定向量的欧几里得距离
double temp = 0.0;
//具体计算(x-x1)^2+(y-y1)^2+(z-z1)^2+...+
for (int j = 0; j < Const.MATRIX_COL; j++) {
temp+= Math.pow(arr[j]-context.data[i][j],2);
}
//每一行的结果保存在一个数组中
result[i] = temp;
}
long end = System.currentTimeMillis();
System.out.println("普通方法"+(end-start)+"ms");
1回答
-
liuyubobobo
2018-06-29
大赞使用索引堆！：）
活学活用看来真的掌握了！：）
我不太确定你使用的场景。首先，如果用java是8s的话，用C++会快很多：）
由于你的数据量足够大，所以有可能（只是有可能）一些简单的优化是有效的，比如把temp的声明放在循环外面：）
这是非常好的可以并行计算的场景。因为指定向量和100万个已知向量之间的计算是互相独立的：）
可以试一下把你的程序中单独元素的计算转换成矩阵计算，可能会快。如果你看过我的课程《机器学习入门》，或者自己会使用numpy的话，可以使用numpy试一下。numpy内置的矩阵运算函数有很多优化。（或者使用Java语言中优化的矩阵运算库，不过我不太了解了）
最后，这个问题很像在做kNN算法，整个问题整体可以使用KD-tree优化，有兴趣可以上网自行研究学习一下KD-Tree这种数据结构和KD-Tree在kNN算法中的应用：）
暂时想到这么多：）
单独求解欧拉距离，是没有更快的算法的。对于两个n维向量，求解这两个向量之间的欧拉距离，每个维度都必须遍历一遍，时间复杂度至少是O(n)的：）
加油！
212018-06-29
相似问题