Python中的三点相关函数

Question

我需要计算在二维空间中一组点的三点空间相关函数 P(r1, r2)。现在我做法是遍历所有的三点组合，计算每组点之间的距离 r1 和 r2，然后绘制一个二维直方图，这样就能得到我想要的三点相关性。不过，这个方法即使对于数量适中的点来说，也花费了很多时间。

我的问题是，有没有办法加快这个计算的速度呢？

r1 = []
r2 = []
points = [[numpy.random.random(1), numpy.random.random(1)] for i in range(100)]
for x in points:
    for y in points:
        for z in points:                
            r1.append(scipy.spatial.distance.euclidean(x, y))
            r2.append(scipy.spatial.distance.euclidean(x, z))

pylab.figure()
n, xedges, yedges = numpy.histogram2d(r1, r2, bins = 10)
pylab.imshow(n, interpolation='nearest', origin='low',
             extent=[xedges[0], xedges[-1], yedges[0], yedges[-1]])

Answer 1

for x in points:
    for y in points:
        r1.append(scipy.spatial.distance.euclidean(x, y))
    for z in points:
        r2.append(scipy.spatial.distance.euclidean(x, z))

这样做可以把复杂度从三次方降低到二次方。我不能给出更多建议，因为我对这个问题的具体情况不太了解。

Answer 2

有几个方法可以让这个过程更快：

首先，对于你的点数组，不需要使用嵌套的长度为1的数组，而是可以直接创建一个 Nx2 的数组，这样会更简洁：

points = np.random.random((N, 2))

接下来，你会发现自己计算每对距离的次数太多了。其实只需要计算一次每个距离，然后再遍历数组的元素就可以了。Scipy库可以帮你完成这个计算，使用 scipy.spatial.distance.pdist。如果你想得到一个成对距离的矩阵，就需要用到 scipy.spatial.distance.squareform。如果你想手动遍历矩阵的元素：

r1 = []
r2 = []
d = squareform(pdist(points))
for i in range(N):
    for j in range(N):
        for k in range(N):
            r1.append(d[i,j])
            r2.append(d[i,k])

最后，你可以更简单地理解成对距离矩阵 d 和输出 r1、r2 之间的关系（你可以通过观察一些小的 N 值，比如3，来发现这个关系）。通过一些数组操作，你可以用以下方法得到相同的数组：

d = squareform(pdist(points))
r1 = np.tile(d.reshape((N**2, 1)), N).flatten()
r2 = np.tile(d, N).flatten()

在我的慢电脑上，使用一个适中的 N=20，你的代码运行需要1.15秒，而显式循环的方法只需12.7毫秒，数组操作的快捷方式只需362微秒，后两者的性能应该比原始代码更好。