numpy中获取数组中n对乘积距离的最快方法

Question

我有N个点数，例如：

A = [2, 3]
B = [3, 4]
C = [3, 3]
.
.
.

它们在一个数组中，如下所示：

arr = np.array([[2, 3], [3, 4], [3, 3]])

我需要 BFS (Breadth First Search) 中的所有成对距离作为输出，以便跟踪哪个距离是哪个距离，例如：A->B, A->C, B->C。对于上面的示例数据，结果将是 [1.41, 1.0, 1.0].

编辑：我必须使用 numpy 或核心库来完成它。

Answer 1

如果你可以使用它，SciPy有一个功能：

In [2]: from scipy.spatial.distance import pdist

In [3]: pdist(arr)
Out[3]: array([1.41421356, 1.        , 1.        ])

Answer 2

这是一个 numpy-only 解决方案（公平警告：它需要大量内存，不像 pdist）...

dists = np.triu(np.linalg.norm(arr - arr[:, None], axis=-1)).flatten()
dists = dists[dists != 0]

演示：

In [4]: arr = np.array([[2, 3], [3, 4], [3, 3], [5, 2], [4, 5]])

In [5]: pdist(arr)
Out[5]:
array([1.41421356, 1.        , 3.16227766, 2.82842712, 1.        ,
       2.82842712, 1.41421356, 2.23606798, 2.23606798, 3.16227766])

In [6]: dists = np.triu(np.linalg.norm(arr - arr[:, None], axis=-1)).flatten()

In [7]: dists = dists[dists != 0]

In [8]: dists
Out[8]:
array([1.41421356, 1.        , 3.16227766, 2.82842712, 1.        ,
       2.82842712, 1.41421356, 2.23606798, 2.23606798, 3.16227766])

时间（上面的解决方案包含在一个名为 triu 的函数中）：

In [9]: %timeit pdist(arr)
7.27 µs ± 738 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [10]: %timeit triu(arr)
25.5 µs ± 4.58 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Answer 3

作为替代方法，但类似于，我们可以使用np.triu_indices，其中return只是矩阵中的上三角索引，可能更多memory-efficient:

np.linalg.norm(arr - arr[:, None], axis=-1)[np.triu_indices(arr.shape[0], 1)]

这不需要展平和索引等额外模块。它的性能类似于前面提到的大数据答案（例如，您可以通过 arr = np.random.rand(10000, 2) 在 colab 上进行检查，两者都将在 4.6 秒左右完成；它可能比 np.triu 和 flatten 在更大的数据中）。

我已经通过memory-profiler测试了一次内存使用，如下所示，但如果它对内存使用很重要，则必须再次检查（我不确定）：

更新：

我试图将计算限制在上三角，这使测试数组上的代码速度提高了 2 到 3 倍。随着数组大小的增长，此循环与之前 np.triu_indices 或 np.triu 方法之间的性能差异越来越大，并且更加明显：

ind = np.arange(arr.shape[0] - 1)
sub_ind = ind + 1
result = np.zeros(sub_ind.sum())
j = 0
for i in range(ind.shape[0]):
    result[j:j+ind[-1-i]+1] = np.linalg.norm(arr[ind[i]] - arr[sub_ind[i]:], axis=-1)
    j += ind[-1-i]+1

另外，通过这种方式，至少减少了内存消耗~x4。因此，这种方法可以更快地处理更大的数组。

Benchmarks:

# arr = np.random.rand(100, 2)
100 loops, best of 5: 459  µs per loop     (ddejohns --> np.triu & np.flatten) 
100 loops, best of 5: 528  µs per loop     (mine --> np.triu_indices) 
100 loops, best of 5: 1.42 ms per loop     (This method)
--------------------------------------
# arr = np.random.rand(1000, 2)
10  loops, best of 5: 49.9 ms per loop
10  loops, best of 5: 49.7 ms per loop
10  loops, best of 5: 30.4 ms per loop      (~x1.7)  The fastest
--------------------------------------
# arr = np.random.rand(10000, 2)
2   loops, best of 5: 4.56 s  per loop
2   loops, best of 5: 4.6  s  per loop
2   loops, best of 5: 1.85 s  per loop      (~x2.5)  The fastest

numpy中获取数组中n对乘积距离的最快方法

Fastest way in numpy to get distance of product of n pairs in array

python

arrays

python-3.x

numpy

bigdata

更新：

Benchmarks: