Matlab/Octave算法示例:
input vector: [ 1 0 2 0 7 7 7 0 5 0 0 0 9 ]
output vector: [ 1 1 2 2 7 7 7 7 5 5 5 5 9 ]
该算法非常简单:它遍历向量并用最后一个非零值替换所有零。这看起来微不足道,当用一个缓慢的 for (i=1:length) 循环完成并能够引用前一个元素 (i-1) 时也是如此,但看起来不可能以快速矢量化形式表达。 我尝试了 merge() 和 shift() 但它只适用于第一次出现的零,而不适用于任意数量的零。
它可以在 Octave/Matlab 中以矢量化形式完成,还是必须使用 C 才能在大量数据上具有足够的性能?
我有another similar slow for-loop algorithm to speed up并且通常不可能以矢量化形式引用以前的值,例如 SQL lag()
或 group by
或 loop (i-1)
很容易做到。但是 Octave/Matlab 循环非常慢。
有没有人找到这个一般问题的解决方案,或者出于基本的 Octave/Matlab 设计原因,这是徒劳的?
性能基准:
解决方案 1(慢循环)
in = repmat([ 1 0 2 0 7 7 7 0 5 0 0 0 9 ] ,1 ,100000);
out = in;
tic
for i=2:length(out)
if (out(i)==0)
out(i)=out(i-1);
end
end
toc
[in(1:20); out(1:20)] % test to show side by side if ok
耗时是 15.047 秒。
Dan 的解决方案 2(快约 80 倍)
in = V = repmat([ 1 0 2 0 7 7 7 0 5 0 0 0 9 ] ,1 ,100000);
tic;
d = double(diff([0,V])>0);
d(find(d(2:end))+1) = find(diff([0,~V])==-1) - find(diff([0,~V])==1);
out = V(cumsum(~~V+d)-1);
toc;
[in(1:20); out(1:20)] % shows it works ok
耗时是 0.188167 秒。
15.047/0.188167 = 79.97 倍改进
GameOfThrows 的解决方案 3(快约 115 倍)
in = repmat([ 1 0 2 0 7 7 7 0 5 0 0 0 9 ] ,1 ,100000);
a = in;
tic;
pada = [a,888];
b = pada(pada >0);
bb = b(:,1:end-1);
c = find (pada==0);
d = find(pada>0);
len = d(2:end) - (d(1:end-1));
t = accumarray(cumsum([1,len])',1);
out = bb(cumsum(t(1:end-1)));
toc;
耗时是 0.130558 秒。
15.047/0.130558 = 115.25 倍改进
神奇 Luis Mendo 的解决方案 4 (快约 250 倍)
in = repmat([ 1 0 2 0 7 7 7 0 5 0 0 0 9 ] , 1, 100000);
tic;
u = nonzeros(in);
out = u(cumsum(in~=0)).';
toc;
耗时是 0.0597501 秒。
15.047/0.0597501 = 251.83 倍改进
(更新 2019/03/13)使用 MATLAB R2017a 的时间安排:
Slow loop: 0.010862 seconds.
Dan: 0.072561 seconds.
GameOfThrows: 0.066282 seconds.
Luis Mendo: 0.032257 seconds.
fillmissing: 0.053366 seconds.
因此我们再次得出相同的结论:MATLAB 中的循环不再慢!
另见: Trivial/impossible algorithm challenge in Octave/Matlab Part II: iterations memory
最佳答案
下面的简单方法可以满足您的需求,而且速度可能非常快:
in = [1 0 2 0 7 7 7 0 5 0 0 0 9];
t = cumsum(in~=0);
u = nonzeros(in);
out = u(t).';
关于arrays - 用先前的非零值替换向量中的所有零,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34041614/