algorithm - 我该如何优化这个索引算法

Question

我的问题

• 有什么办法可以加快计算速度吗？
• 是否有更好的算法或实现可用于计算相同的值？

描述算法

我有一个复杂的索引问题，我正在努力以有效的方式解决。

目标是计算矩阵 w_prime 使用来自大小相等的矩阵 w、dY 和 的值的组合值>dX。

w_prime(i,j) 的值计算为 mean( w( indY & indX ) )，其中 indY 和 indX 是 dY 和 dX 的索引，分别等于 i 和 j .

下面是计算 w_prime 的算法在 matlab 中的简单实现:

for i = 1:size(w_prime,1)
  indY = dY == i;
  for j = 1:size(w_prime,2)
    indX = dX == j; 
    w_prime(ind) = mean( w( indY & indX ) );
  end
end

性能问题

这个实现在下面的例子中就足够了；然而，在我的实际用例中，w、dY、dX 是 ~3000x3000 和 w_prime 是 ~60X900。这意味着每个索引计算都发生在约 900 万个元素上。不用说，这个实现太慢而无法使用。此外，我需要运行此代码几十次。

示例计算

如果我想计算w(1,1)

• 找到dY中等于1的索引，保存为indY
• 找到dX中等于1的索引，保存为indX

• 找到 indY 和 indX 的交集，保存为 ind

• 将mean( w(ind) ) 保存到w_prime(1,1)

一般问题描述

我有一个由两个向量 X 和 T 定义的设定点，它们都是 1XN，其中 N 约为 3000。此外，X 和 T 的值是分别受区间 (1 60) 和 (1 900) 约束的整数。

矩阵 dX 和 dT 只是距离矩阵，这意味着它们包含点之间的成对距离。即 dx(i,j) 等于 abs( x(i) - x(j) )。

它们是使用以下方法计算的:dx = pdist(x);

矩阵 w 可以被认为是一个权重矩阵，描述了一个点对另一个点的影响程度。

计算w_prime(a,b)的目的是确定中a分隔的点子集之间的平均权重X 维度和T 维度中的b。

这可以表示如下:

Answer 1

这很简单 ACCUMARRAY :

nx = max(dX(:));
ny = max(dY(:));

w_prime = accumarray([dX(:),dY(:)],w(:),[nx,ny],@mean,NaN)

输出将是一个 nx-by-ny 大小的数组，只要没有对应的索引对，就会包含 NaN。如果您确定始终存在完整的索引，则可以将上述计算简化为

w_prime = accumarray([dX(:),dY(:)],w(:),[],@mean)

那么，accumarray 有什么作用？它查看 [dX(:),dY(:)] 的行。每行给出 w_prime 中该行贡献的 (i,j) 坐标对。对于所有对 (1,1)，它将函数 (@mean) 应用于 w(:) 中的相应条目，并写入输出到 w_prime(1,1)。