matlab - 有没有办法避免循环使这段代码更快？

Question

有没有办法避免循环使这段代码更快？

“var”是期望的结果。

“AA”和“BB”是其值已知的向量。

此代码的四个主要行基于以下逻辑:00 , 01 , 10 , 11 ( 0 对于 <= 和 1 对于 > )

for i=3:1:2000

    for j=1:50011
        if AA(i) == j && BB(i)<=BB(i-1) && BB(i-1)<=BB(i-2)
           var(i)=j;
        else
            if AA(i) == j && BB(i)<=BB(i-1) && BB(i-1)>BB(i-2)
               var(i)=j+50011;
            else
                if AA(i) == j && BB(i)>BB(i-1) && BB(i-1)<=BB(i-2)
                   var(i)=j+2*50011;
                else
                    if AA(i) == j && BB(i)>BB(i-1) && BB(i-1)>BB(i-2)
                       var(i)=j+3*50011;
                    end
                end
            end
        end
    end

end

Answer 1

我设法将您的代码矢量化为一行代码!从几秒缩短到不到一毫秒:

out = [0 0 AA(3:end) + ([1 2] * (diff(BB(hankel(1:3, 3:numel(BB)))) > 0)).*50011];

要了解如何到达那里，让我们逐步改进原始代码。

---

1)

首先我们从您拥有的双循环开始:

tic
var0 = zeros(size(AA));
for i=3:numel(AA)
    for j=1:N
        if AA(i) == j && BB(i)<=BB(i-1) && BB(i-1)<=BB(i-2)
            var0(i)=j;
        else
            if AA(i) == j && BB(i)<=BB(i-1) && BB(i-1)>BB(i-2)
                var0(i)=j+50011;
            else
                if AA(i) == j && BB(i)>BB(i-1) && BB(i-1)<=BB(i-2)
                    var0(i)=j+2*50011;
                else
                    if AA(i) == j && BB(i)>BB(i-1) && BB(i-1)>BB(i-2)
                        var0(i)=j+3*50011;
                    end
                end
            end
        end
    end
end
toc

2)

正如@SpamBot 指出的那样，嵌套的 if/else 语句可以通过链接来简化。此外，您正在多次评估相同的测试 AA(i)==j 。如果测试为假，则跳过整个 for 循环。所以我们可以去掉这第二个for循环，直接使用j=AA(i)。

这是新的代码:

tic
var1 = zeros(size(AA));
for i=3:numel(AA)
    j = AA(i);
    if BB(i)<=BB(i-1) && BB(i-1)<=BB(i-2)
        var1(i) = j;
    elseif BB(i)<=BB(i-1) && BB(i-1)>BB(i-2)
        var1(i) = j + 50011;
    elseif BB(i)>BB(i-1) && BB(i-1)<=BB(i-2)
        var1(i) = j + 2*50011;
    elseif BB(i)>BB(i-1) && BB(i-1)>BB(i-2)
        var1(i) = j + 3*50011;
    end
end
toc

这是一个巨大的改进，代码的运行时间仅为原来的一小部分。我们仍然可以做得更好...

3)

正如您在问题中提到的，if/else 条件对应于模式 00、01、10、11，其中 0/1 或 false/true 是执行二进制 x> 的结果y 测试相邻数字。

利用这个思路，我们得到如下代码:

tic
var2 = zeros(size(AA));
for i=3:numel(AA)
    val = (BB(i) > BB(i-1)) * 10 + (BB(i-1) > BB(i-2));
    switch (val)
        case 00
            k = 0;
        case 01
            k = 50011;
        case 10
            k = 2*50011;
        case 11
            k = 3*50011;
    end
    var2(i) = AA(i) + k;

end
toc

4)

让我们用表查找操作替换该 switch 语句。这给了我们这个新版本:

tic
v = [0 1 2 3] * 50011;  % 00 01 10 11
var3 = zeros(size(AA));
for i=3:numel(AA)
    var3(i) = AA(i) + v((BB(i) > BB(i-1))*2 + (BB(i-1) > BB(i-2)) + 1);
end
toc

5)

在这个最终版本中，我们可以通过注意每次迭代都以滑动窗口方式访问切片 BB(i-2:i) 来完全摆脱循环。我们可以整齐use the hankel function to create a sliding window BB(每个都作为一列返回)。

接下来我们使用 diff 执行矢量化比较，然后将两个测试的结果 0/1 映射为 [0 1 2 3]*50011 值。最后，我们适本地添加向量 AA。

这给了我们最后的一行，完全矢量化:

tic
var4 = [0, 0, AA(3:end) + ([1 2] * (diff(BB(hankel(1:3, 3:numel(BB)))) > 0)).*50011];
toc

---

比较

为了验证上述解决方案，我使用了以下随机向量作为测试数据:

N = 50011;
AA = randi(N, [1 2000]);
BB = randi(N, [1 2000]);

assert(isequal(var0,var1,var2,var3,var4))

我得到以下时间，按顺序匹配解决方案:

>> myscript  % tested in MATLAB R2014a
Elapsed time is 1.663210 seconds.
Elapsed time is 0.000111 seconds.
Elapsed time is 0.000099 seconds.
Elapsed time is 0.000089 seconds.
Elapsed time is 0.000417 seconds.

>> myscript  % tested in MATLAB R2015b (with the new execution engine)
Elapsed time is 2.816541 seconds.
Elapsed time is 0.000233 seconds.
Elapsed time is 0.000158 seconds.
Elapsed time is 0.000157 seconds.
Elapsed time is 0.000339 seconds.

希望这篇文章不会太长，我只是想展示如何通过进行增量更改来解决此类问题。

现在选择您最喜欢的解决方案:)