如何优化此索引算法

Question

我的问题

• 无论如何,我可以加快这个计算吗？
• 是否有更好的算法或实现可用于计算相同的值？

描述算法

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

我们的目标是计算矩阵w_prime使用值从相同大小的矩阵值的组合w,dY和dX.

值的w_prime(i,j)计算方式为mean( w( indY & indX ) ),其中indY和indX是指数dY和dX它们分别等于i和j.

这是一个用于计算算法的matlab中的简单实现w_prime:

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的值分别是由间隔(160)和(1 900)限定的整数.

矩阵dX和dT简单的距离矩阵,意味着它们包含点之间的成对距离.也许dx(i,j)是平等的abs( x(i) - x(j) ).

它们的计算方法如下: dx = pdist(x);

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

计算的目的w_prime(a,b)是要确定由分开的点的子集之间的平均重量a在X尺寸和b在T尺寸.

这可以表示如下:

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(:)].每行给出行所贡献的(i,j)坐标对w_prime.对于所有对(1,1),它将函数(@mean)应用于相应的条目w(:),并将输出写入w_prime(1,1).