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

Question

我需要在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

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

Answer 1

我知道在NumPy中计算欧几里德距离的最快方法是scikit-learn中的那个,可以概括为

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

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

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

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

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

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