相关疑难解决方法(0)

考虑以下图像，存储为 numpy 数组：

a = [[0,0,0,0,0,1,1,0,0,0],
     [0,0,0,0,1,1,1,1,0,0],
     [0,0,0,0,0,1,1,0,0,0],
     [0,0,0,0,0,0,0,0,0,0],
     [0,0,0,0,0,2,0,0,0,0],
     [0,0,0,0,0,2,2,0,0,0],
     [0,0,0,0,0,2,0,0,0,0],
     [0,0,0,0,3,3,3,0,0,0],
     [4,0,0,0,0,0,0,0,0,0],
     [4,4,0,0,0,0,0,0,0,0],
     [4,4,4,0,0,0,0,0,0,0]]

a = np.array(a)

零代表背景像素，1、2、3 和 4 代表属于对象的像素。您可以看到对象总是在图像中形成连续的岛屿或区域。我想知道每对物体之间的距离。作为距离度量，我希望在对象的那些像素之间具有最短的直线距离，它们彼此最接近。示例：Distance(2,3) = 1，因为它们在接触。Distance(1,2) = 2，因为正好有一个背景像素将两个区域分开，或者换句话说，对象的最近像素相隔两个像素。

谁能告诉我如何在 Python 中解决这个问题？或者给我链接一些资源？

考虑一个维数NxM的numpy数组A. 目标是计算欧几里德距离矩阵D,其中每个元素D [i,j]是行i和j之间的核心距离.这样做的最快方法是什么？这不是我需要解决的问题,但它是我正在尝试做的一个很好的例子(通常,可以使用其他距离度量).

这是迄今为止我能想到的最快的:

n = A.shape[0]
D = np.empty((n,n))
for i in range(n):
    D[i] = np.sqrt(np.square(A-A[i]).sum(1))

但这是最快的方式吗？我主要关注for循环.我们可以用Cython打败这个吗？

为了避免循环,我尝试使用广播,并执行以下操作:

D = np.sqrt(np.square(A[np.newaxis,:,:]-A[:,np.newaxis,:]).sum(2))

但事实证明这是一个坏主意,因为构建维度NxNxM的中间3D阵列会产生一些开销,因此性能更差.

我试过Cython.但我是Cython的新手,所以我不知道我的尝试有多好:

def dist(np.ndarray[np.int32_t, ndim=2] A):
    cdef int n = A.shape[0]    
    cdef np.ndarray[np.float64_t, ndim=2] dm = np.empty((n,n), dtype=np.float64)      
    cdef int i = 0    
    for i in range(n):  
        dm[i] = np.sqrt(np.square(A-A[i]).sum(1)).astype(np.float64)              
    return dm 

上面的代码比Python的for循环慢一点.我对Cython知之甚少,但我认为我可以达到至少与for loop + numpy相同的性能.我想知道在正确的方式下是否有可能实现一些显着的性能提升？或者是否还有其他方法可以加快速度(不涉及并行计算)？

我试图计算由于重力引起的3空间n体问题的加速度(我使用辛欧拉).

我有每个时间步的位置和速度矢量,并使用下面(工作)代码来计算加速度并更新速度和位置.请注意,加速度是3空间中的矢量,而不仅仅是幅度.

我想知道是否有更有效的方法来计算这个与numpy以避免循环.

def accelerations(positions, masses):
    '''Params:
    - positions: numpy array of size (n,3)
    - masses: numpy array of size (n,)
    Returns:
    - accelerations: numpy of size (n,3), the acceleration vectors in 3-space
    '''
    n_bodies = len(masses)
    accelerations = numpy.zeros([n_bodies,3]) # n_bodies * (x,y,z)

    # vectors from mass(i) to mass(j)
    D = numpy.zeros([n_bodies,n_bodies,3]) # n_bodies * n_bodies * (x,y,z)
    for i, j in itertools.product(range(n_bodies), range(n_bodies)):
        D[i][j] = positions[j]-positions[i]

    # Acceleration due to gravitational force between each pair of bodies
    A …

我有一个关于如何尽可能快地计算numpy距离的问题,

def getR1(VVm,VVs,HHm,HHs):
    t0=time.time()
    R=VVs.flatten()[numpy.newaxis,:]-VVm.flatten()[:,numpy.newaxis]
    R*=R
    R1=HHs.flatten()[numpy.newaxis,:]-HHm.flatten()[:,numpy.newaxis]
    R1*=R1
    R+=R1
    del R1
    print "R1\t",time.time()-t0, R.shape, #11.7576191425 (108225, 10500) 
    print numpy.max(R) #4176.26290975
    # uses 17.5Gb ram
    return R


def getR2(VVm,VVs,HHm,HHs):
    t0=time.time()
    precomputed_flat = numpy.column_stack((VVs.flatten(), HHs.flatten()))
    measured_flat = numpy.column_stack((VVm.flatten(), HHm.flatten()))
    deltas = precomputed_flat[None,:,:] - measured_flat[:, None, :]
    #print time.time()-t0, deltas.shape # 5.861109972 (108225, 10500, 2)
    R = numpy.einsum('ijk,ijk->ij', deltas, deltas)
    print "R2\t",time.time()-t0,R.shape, #14.5291359425 (108225, 10500)
    print numpy.max(R) #4176.26290975
    # uses 26Gb ram
    return R


def getR3(VVm,VVs,HHm,HHs):
    from numpy.core.umath_tests import inner1d
    t0=time.time()
    precomputed_flat = …

问题： 我有一个大约为 [350000, 1] 的向量，我希望计算成对距离。这导致 [350000, 350000] 整数数据类型的矩阵不适合 RAM。我最终想得到一个布尔值（适合 RAM），所以我目前一次只做一个元素，但这不是很节省时间。

编辑：由于数据的大小，标准 sklearn 和 scipy 函数不起作用 - 但如果我可以以某种方式将其分块以使用硬盘，那么我应该能够使用这些。

问题可视化： [a_1, a_2, a_3]^t -> [[a_1 - a_1, a_1 - a_2, a_1 - a_3], [a_2 - a_1, a_2 - a_2, a_2 - a_3], [a_3 - a_1, a_3 - a_2, a_3 - a_3]]

请注意，取绝对值时，只需要计算上三角形，因为它是对称的。

需要分块或替代解决方案的矢量化代码： 我找到了一种方法来计算使用广播在小矩阵上工作的所有点之间的距离（减法），但需要一种方法来在不达到 RAM 限制的情况下在更大的矩阵上执行此操作。

或者也许可以建议更好的方法来更快地访问下面的 MWE？

distMatrix = np.absolute((points[np.newaxis, :, :] - points[:, np.newaxis, :])[:, :, 0])

其他尝试： 我尝试使用 dask 和 memmap 但仍然出现内存错误，所以一定是做错了什么。我也尝试过 memmap 并手动对数据进行分块，但没有获得完整的结果集，因此非常感谢任何帮助。

当前方法的 MWE：

## Data ## …