performance - 是否可以加速此 MATLAB 脚本？

Question

我遇到了一些性能问题，因此我想加快那些运行缓慢的脚本的速度。但是我对如何加快它们的速度没有更多的想法。因为我发现我经常被索引阻塞。我发现抽象思维对我来说非常困难。

脚本是

    tic,
    n = 1000;
    d = 500;
    X = rand(n, d);
    R = rand(n, n);
    F = zeros(d, d);
    for i=1:n
        for j=1:n
           F = F + R(i,j)* ((X(i,:)-X(j,:))' * (X(i,:)-X(j,:)));
        end
    end
    toc

Answer 1

讨论和解决代码

这里可以推荐一些使用bsxfun 的方法。此外，请继续阅读以了解如何在解决此类问题时获得 30x+ 加速!

方法 #1(朴素矢量化方法)

为了适应 X 的行之间的两个减法运算，然后在它们之间进行后续的逐元素乘法运算，一个朴素的基于 bsxfun 的方法将导致 4D 中间体对应于 ((X(i,:)-X(j,:))' * (X(i,:)-X(j,:))) 的数组。之后，需要乘以 R 以获得最终输出 F。这是如下所示实现的-

v1 = bsxfun(@minus,X,permute(X,[3 2 1]));
v2 = bsxfun(@times,permute(v1,[1 3 2]),permute(v1,[1 3 4 2]));
F = reshape(R(:).'*reshape(v2,[],d^2),d,[]);

方法 #2(不那么简单的矢量化方法)

前面提到的方法进入 4D，这可能会减慢速度。因此，您可以通过 reshape 将中间数据保留到 3D。接下来列出 -

sub1 = bsxfun(@minus,X,permute(X,[3 2 1]));
sub1_2d = reshape(permute(sub1,[1 3 2]),n^2,[])
mult1 = bsxfun(@times,sub1_2d,permute(sub1_2d,[1 3 2]))
F = reshape(R(:).'*reshape(mult1,[],d^2),d,[])

方法 #3(混合方法)

现在，您可以基于方法 #2(向量减法 + 循环乘法)创建混合方法。这种方法的好处是它使用快速矩阵乘法来执行乘法并将复杂度从早期的 O(n^2) 降低到 O(n)，这应该会使其更加高效.感谢@Dev-iL，提出这个想法!这是代码-

sub1 = bsxfun(@minus,X,permute(X,[3 2 1]));
sub1 = bsxfun(@times,sub1,permute(sqrt(R),[1 3 2]));

F = zeros(d);
for k = 1:size(sub1,3)
    blk = sub1(:,:,k);    
    F = F + blk.'*blk;
end

---

基准测试

将原始方法与方法 #3 进行比较的基准代码

%// Parameters
n = 500;
d = 250;
X = rand(n, d);
R = rand(n, n);

%// Warm up tic/toc.
for k = 1:100000
    tic(); elapsed = toc();
end

disp('------------------------------ With Original Approach')
tic
F1 = zeros(d, d);
for i=1:n
    for j=1:n
        F1 = F1 + R(i,j)*((X(i,:)-X(j,:))' * (X(i,:)-X(j,:)));
    end
end
toc, clear F1 i j

disp('------------------------------ With Proposed Approach #3')
tic
sub1 = bsxfun(@minus,X,permute(X,[3 2 1]));
sub1 = bsxfun(@times,sub1,permute(sqrt(R),[1 3 2]));

F = zeros(d);
for k = 1:size(sub1,3)
    blk = sub1(:,:,k);    
    F = F + blk.'*blk;
end
toc

运行时结果

------------------------------ With Original Approach
Elapsed time is 29.728571 seconds.
------------------------------ With Proposed Approach #3
Elapsed time is 0.839726 seconds.

那么，谁准备好接受 30x+ 加速了!？