使用Numpy有效地计算欧几里得距离矩阵

Question

我在二维空间中有一组点，需要计算每个点到另一个点的距离。

我的点数相对较少，最多不超过100个。但是，由于我需要经常快速地确定这些移动点之间的关系，并且因为我知道遍历这些点可能同样糟糕由于O（n ^
2）的复杂性，我正在寻找利用numpy矩阵魔术（或scipy）的方法。

就象我的代码中所说的那样，每个对象的坐标都存储在其类中。但是，当我更新类坐标时，也可以用numpy数组更新它们。

class Cell(object):
    """Represents one object in the field."""
    def __init__(self,id,x=0,y=0):
        self.m_id = id
        self.m_x = x
        self.m_y = y

我想到创建一个欧几里得距离矩阵来防止重复，但是也许您有一个更聪明的数据结构。

我也很喜欢漂亮算法的指针。

此外，我注意到存在类似的问题，涉及欧几里得距离和numpy，但没有找到直接解决有效填充全距离矩阵这一问题的任何问题。

Answer 1

您可以利用以下complex类型：

# build a complex array of your cells
z = np.array([complex(c.m_x, c.m_y) for c in cells])

第一个解决方案

# mesh this array so that you will have all combinations
m, n = np.meshgrid(z, z)
# get the distance via the norm
out = abs(m-n)

第二解决方案

网格划分是主要思想。但它numpy很聪明，因此您不必生成m＆n。只需使用的转置版本计算差异即可z。网格自动完成：

out = abs(z[..., np.newaxis] - z)

第三种解决方案

如果z直接设置为二维数组，则可以使用z.T而不是weird z[..., np.newaxis]。所以最后，您的代码将如下所示：

z = np.array([[complex(c.m_x, c.m_y) for c in cells]]) # notice the [[ ... ]]
out = abs(z.T-z)

例

>>> z = np.array([[0.+0.j, 2.+1.j, -1.+4.j]])
>>> abs(z.T-z)
array([[ 0.        ,  2.23606798,  4.12310563],
       [ 2.23606798,  0.        ,  4.24264069],
       [ 4.12310563,  4.24264069,  0.        ]])

作为补充，您以后可能想删除重复项，取上三角形：

>>> np.triu(out)
array([[ 0.        ,  2.23606798,  4.12310563],
       [ 0.        ,  0.        ,  4.24264069],
       [ 0.        ,  0.        ,  0.        ]])

一些基准

>>> timeit.timeit('abs(z.T-z)', setup='import numpy as np;z = np.array([[0.+0.j, 2.+1.j, -1.+4.j]])')
4.645645342274779
>>> timeit.timeit('abs(z[..., np.newaxis] - z)', setup='import numpy as np;z = np.array([0.+0.j, 2.+1.j, -1.+4.j])')
5.049334864854522
>>> timeit.timeit('m, n = np.meshgrid(z, z); abs(m-n)', setup='import numpy as np;z = np.array([0.+0.j, 2.+1.j, -1.+4.j])')
22.489568296184686