python – 计算平方欧氏距离的可能优化

发布时间：2020-12-20 12:24:41 所属栏目：Python 来源：网络整理

导读：我需要在 Python项目中每天进行几亿次欧氏距离计算. 这是我开始的： def euclidean_dist_square(x,y): diff = np.array(x) - np.array(y) return np.dot(diff,diff) 这是非常快的,我已经放弃了sqrt计算,因为我只需要对项目进行排名(最近邻搜索).尽管如此,它

我需要在 Python项目中每天进行几亿次欧氏距离计算.

这是我开始的：

def euclidean_dist_square(x,y):
    diff = np.array(x) - np.array(y)
    return np.dot(diff,diff)

这是非常快的,我已经放弃了sqrt计算,因为我只需要对项目进行排名(最近邻搜索).尽管如此,它仍然是剧本的瓶颈.因此我编写了一个C扩展,用于计算距离.始终使用128维向量进行计算.

#include "euclidean.h"
#include <math.h>

double euclidean(double x[128],double y[128])
{
    double Sum;
    for(int i=0;i<128;i++)
    {
        Sum = Sum + pow((x[i]-y[i]),2.0);
    }
    return Sum;
}

扩展的完整代码如下：https://gist.github.com/herrbuerger/bd63b73f3c5cf1cd51de

现在,与numpy版本相比,这提供了一个很好的加速.

但有没有办法进一步加快这一点(这是我的第一个C扩展,所以我假设有)？随着每天使用此功能的次数,每微秒实际上会提供一个好处.

你们中的一些人可能会建议将这完全从Python移植到另一种语言,不幸的是,这是一个更大的项目而不是一个选项:(

谢谢.

编辑

我在CodeReview上发布了这个问题：https://codereview.stackexchange.com/questions/52218/possible-optimizations-for-calculating-squared-euclidean-distance

如果有人开始写答案,我会在一小时内删除这个问题.

解决方法

我知道在NumPy中计算欧氏距离的最快方法是 the one in scikit-learn,可以总结为

def squared_distances(X,Y):
    """Return a distance matrix for each pair of rows i,j in X,Y."""
    # https://stackoverflow.com/a/19094808/166749
    X_row_norms = np.einsum('ij,ij->i',X,X)
    Y_row_norms = np.einsum('ij,Y,Y)
    distances = np.dot(X,Y)
    distances *= -2
    distances += X_row_norms
    distances += Y_row_norms

    np.maximum(distances,distances)  # get rid of negatives; optional
    return distances

这段代码中的瓶颈是矩阵乘法(np.dot),因此请确保您的NumPy与良好的BLAS实现相关联;在多核机器上使用多线程BLAS和足够大的输入矩阵,它应该比你在C中提供的任何东西都要快.注意它依赖于二项式公式

||x - y||2 = ||x||2 + ||y||2 - 2 x?y

并且可以跨k-NN用例的调用缓存X_row_norms或Y_row_norms.

(我是这段代码的合着者,我花了很多时间来优化它和SciPy实现; scikit-learn更快,但牺牲了一些准确性,但对于k-NN来说,这应该不会太重要. scipPy实现(scipy.spatial.distance中提供)实际上是您刚编写的代码的优化版本,并且更准确.)

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!