python中最快的成对距离度量

Question

import numpy as np
import random
r = np.array([random.randrange(1, 1000) for _ in range(0, 1000)])
dists = np.abs(r - r[:, None])

注意：矩阵是对称的，所以我猜测，通过寻址它，至少有可能获得2倍的加速，我只是不知道如何实现。

Answer 1

其他两个答案都没有完全回答问题--1是在Cython中，一个更慢。但两者都提供了非常有用的提示。对它们的跟踪表明scipy.spatial.distance.pdist是一种可行的方法。

下面是一些代码：

import numpy as np
import random
import sklearn.metrics.pairwise
import scipy.spatial.distance

r = np.array([random.randrange(1, 1000) for _ in range(0, 1000)])
c = r[:, None]

def option1(r):
    dists = np.abs(r - r[:, None])

def option2(r):
    dists = scipy.spatial.distance.pdist(r, 'cityblock')

def option3(r):
    dists = sklearn.metrics.pairwise.manhattan_distances(r)

使用IPython计时：

In [36]: timeit option1(r)
100 loops, best of 3: 5.31 ms per loop

In [37]: timeit option2(c)
1000 loops, best of 3: 1.84 ms per loop

In [38]: timeit option3(c)
100 loops, best of 3: 11.5 ms per loop

我没有尝试Cython实现（我不能在此项目中使用它），但将我的结果与其他答案相比较，scipy.spatial.distance.pdist似乎比Cython实现慢了大约三分之一（通过对NP.ABS解决方案进行基准测试，考虑到了不同的机器）。