python - 距离度量的组合优化

Question

我有一组轨迹，由沿着轨迹的点组成，每个点都有相关的坐标。我将它们存储在一个 3d 数组中(轨迹、点、参数)。我想找到一组 r 轨迹，这些轨迹在这些轨迹的可能成对组合之间具有最大累积距离。我认为我的第一次尝试是这样的:

max_dist = 0
for h in itertools.combinations ( xrange(num_traj), r):
    for (m,l) in itertools.combinations (h, 2):
        accum = 0.
        for ( i, j ) in itertools.izip ( range(k), range(k) ):
            A = [ (my_mat[m, i, z] - my_mat[l, j, z])**2 \
                    for z in xrange(k) ]
            A = numpy.array( numpy.sqrt (A) ).sum()
            accum += A
    if max_dist < accum:
        selected_trajectories = h

这需要很长时间，因为 num_traj 可能在 500-1000 左右，而 r 可能在 5-20 左右。 k 是任意的，但通常可以达到 50。

为了变得 super 聪明，我将所有内容都放入两个嵌套列表理解中，大量使用 itertools:

chunk = [[ numpy.sqrt((my_mat[m, i, :] - my_mat[l, j, :])**2).sum() \
        for ((m,l),i,j) in \
        itertools.product ( itertools.combinations(h,2), range(k), range(k)) ]\
        for h in itertools.combinations(range(num_traj), r) ]

除了非常难读 (!!!)，它还需要很长时间。谁能提出任何改进方法？

Answer 1

您可以先计算所有轨迹对之间的距离，而不是按需重新计算每对轨迹之间的距离。您可以将它们存储在字典中并根据需要进行查找。

这样，您的内循环 for (i,j) ... 将被替换为恒定时间查找。