我有一个 N
点的数组,d
维度 (N, d)
我想创建一个新的数组每对 (N choose 2, d)
的所有位移向量。如果我只想要这些向量的大小,我可以使用 pdist
来自 scipy.spatial.distance
.
如果我能做到就好了
pdist(points, lambda u, v: u - v)
但是metric
函数必须返回一个标量(ValueError:用序列设置数组元素。
)
我的解决方案是使用np.triu_indices
:
i, j = np.triu_indices(len(points), 1)
displacements = points[i] - points[j]
这比使用 pdist
慢了大约 20-30 倍(我通过取 displacements
的大小来比较,虽然这不是耗时的部分,我想实际上是在制作上三角并运行花式索引)。
最佳答案
直截了当
dis_vectors = [l - r for l, r in itertools.combinations(points, 2)]
但我怀疑它是否很快。实际上 %timeit
说:
3分:
list : 13 us
pdist: 24 us
但已经有 27 分了:
list : 798 us
pdist: 35.2 us
我们在这里讨论了多少点?
另一种可能性类似
import numpy
from operator import mul
from fractions import Fraction
def binomial_coefficient(n,k):
# credit to http://stackoverflow.com/users/226086/nas-banov
return int( reduce(mul, (Fraction(n-i, i+1) for i in range(k)), 1) )
def pairwise_displacements(a):
n = a.shape[0]
d = a.shape[1]
c = binomial_coefficient(n, 2)
out = numpy.zeros( (c, d) )
l = 0
r = l + n - 1
for sl in range(1, n): # no point1 - point1!
out[l:r] = a[:n-sl] - a[sl:]
l = r
r += n - (sl + 1)
return out
这只是在所有维度上相对于自身“滑动”数组,并在每个步骤中执行(可广播的)减法。请注意,没有考虑重复,也没有相等的对(例如 point1 - point1)。
此函数在 31.3ms
的 1000 点范围内仍然表现良好,而 pdist
在 20.7ms
和列表理解时仍然更快以1.23 s
位居第三。
关于python - 点集之间的成对位移向量,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22390418/