performance - 如何在 Octave 音阶中优化以下双循环？

Question

我有以下 Octave 代码:

dist=0;
for i = 1:length(x);        
    for j = 1:length(y);
        v  = x(i,:) - y(j,:);
        distvect(j) = norm(v);
    endfor 
    dist = dist + min(distvect);
endfor

其中 x 和 y 是大小为 n x 2 和 m x 2 的矩阵。我的主要问题是:我需要多次运行上面的代码。

我很确定有一种方法可以优化它，每次在内部 for 循环中可能只使用一个矩阵而不是 v 向量，但我找不到它。我在网上搜索，找到了一个 arrayfun功能，这可能会有所帮助，但我不知道如何使用。

感谢您的帮助，
格鲁斯

Answer 1

在这种情况下，您可以进行的最佳优化是实现 norm自己利用矩阵乘法，而不是循环遍历各个元素。

回想一下，对于向量值，norm(v)计算 norm(v, 2) ，这是欧几里得距离

norm(v, 2) = (sum (abs (v) .^ 2)) ^ (1/2)

由于您只需要找到最小距离，因此实际上直到稍后才需要取平方根。为了紧凑，让 a = x(i, :) , b = y(j, :) , M = length(x)和 N = length(y) .由于您的变量 v包含差异向量，我们可以扩展 distvect的计算进入

distvect   = norm(v)
           = norm(x(i, :) - y(j, :))
           = norm(a - b)
           = (sum (abs( a - b ) .^ 2)) ^ (1/2)
distvect^2 = sum (abs ( a - b ) .^ 2)

现在，展开二次项， (a - b)^2 = a^2 - 2ab + b^2 ，这使得 abs功能冗余

distvect^2 = sum (sum(a.*a) * ones(1,N) - 2*a*b' + ones(M,1) * sum(b'.*b') )

最后的优化，它将函数应用于多个值。这是通过使用 x 的外部产品来完成的。和 y创建 length(x) 的矩阵通过 length(y)矩阵。然后只需沿每列取最小距离并将结果的平方根相加

xx   = sum(x .* x, 2) * ones(1, length(y))
xy   = x * y'
yy   = ones(length(x), 1) * sum(y' .* y')

dist = sum(sqrt(min(xx - 2.*xy + yy)))