老师好，关于欧几里得距离计算，有没有什么更高效的计算方式？

Question

自己老师布置的一个题目：在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");

Answer 1

liuyubobobo 2018-06-29 05:54:40

大赞使用索引堆！：）

活学活用看来真的掌握了！：）

• 我不太确定你使用的场景。首先，如果用java是8s的话，用C++会快很多：）

• 由于你的数据量足够大，所以有可能（只是有可能）一些简单的优化是有效的，比如把temp的声明放在循环外面：）

• 这是非常好的可以并行计算的场景。因为指定向量和100万个已知向量之间的计算是互相独立的：）

• 可以试一下把你的程序中单独元素的计算转换成矩阵计算，可能会快。如果你看过我的课程《机器学习入门》，或者自己会使用numpy的话，可以使用numpy试一下。numpy内置的矩阵运算函数有很多优化。（或者使用Java语言中优化的矩阵运算库，不过我不太了解了）

• 最后，这个问题很像在做kNN算法，整个问题整体可以使用KD-tree优化，有兴趣可以上网自行研究学习一下KD-Tree这种数据结构和KD-Tree在kNN算法中的应用：）

暂时想到这么多：）

单独求解欧拉距离，是没有更快的算法的。对于两个n维向量，求解这两个向量之间的欧拉距离，每个维度都必须遍历一遍，时间复杂度至少是O(n)的：）

加油！

• 提问者 qq__SuperAlpaca_0 #1

  好的好的，感谢bobo老师?，我去看看矩阵运算，KD-Tree有关内容✌