Python中最快的成对距离度量

Question

我有一个一维数字数组，想计算所有成对的欧几里得距离。我有一种方法（感谢SO）在广播中执行此操作，但是它效率低下，因为它两次计算每个距离。而且它的伸缩性不好。

这是一个示例，它为我提供了1000个数字的数组。

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

我可以使用scipy / numpy / scikit-learn中最快的实现来执行此操作，因为它必须扩展到一维数组具有> 10k值的情况。

注意：矩阵是对称的，所以我猜想通过解决这个问题至少可以使速度提高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解决方案进行基准测试）。