python - 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 解决方案进行基准测试来考虑不同的机器)。