将向量中的所有零替换为前一个非零值。

Question

将向量中的所有零替换为前一个非零值。

26

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以在大量数据上具有足够的性能？

我有另一个类似的缓慢循环算法以加速，但通常无法以向量化的形式引用先前的值，就像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中的循环不再缓慢！

另请参阅：在Octave/Matlab中的微不足道/不可能的算法挑战第二部分：迭代记忆

- Paweł Załuski

1

@GameOfThrows 是的，我也是这么认为的。刚刚加入了我的尝试。 - Dan

1

@Pawel，你能否在Octave中为我们做一个timeit比较，比较这两个答案和一个朴素的for循环解决方案？看看这些选项是否提供了任何性能改进，这将是有趣的。 - Dan

1

@Dan 确定在处理它。 - Paweł Załuski

1

@Pawel 使用isequal可能更容易，而不是使用[in(1:20); out(1:20)]＃test to show side by side if ok。 - Dan

2

@Pawel，你能否尝试一下Luis Mendo的解决方案？我怀疑它应该是最快、最干净的。 - GameOfThrows

显示剩余8条评论

6个回答

7

我认为这是可能的，让我们从基础开始，你想捕获大于0的数字：

 a = [ 1 0 2 0 7 7 7 0 5 0 0 0 9 ] %//Load in Vector
 pada = [a,888];  %//Pad A with a random number at the end to help in case the vector ends with a 0
 b = pada(find(pada >0)); %//Find where number if bigger than 0
 bb = b(:,1:end-1);     %//numbers that are bigger than 0
 c = find (pada==0);   %//Index where numbers are 0
 d = find(pada>0);     %//Index where numbers are greater than 0
 length = d(2:end) - (d(1:end-1));  %//calculate number of repeats needed for each 0 trailing gap.
 %//R = [cell2mat(arrayfun(@(x,nx) repmat(x,1,nx), bb, length,'uniformoutput',0))]; %//Repeat the value

 ----------EDIT--------- 
 %// Accumarray and cumsum method, although not as nice as Dan's 1 liner
 t = accumarray(cumsum([1,length])',1);
 R = bb(cumsum(t(1:end-1)));

注意：我使用了arrayfun，但你也可以使用accumarray。我认为这证明了可以并行处理这个问题？

R =

第1列到第10列

 1     1     2     2     7     7     7     7     5     5

第11到13列

 5     5     9

测试：

a = [ 1 0 2 0 7 7 7 0 5 0 0 0 9 0 0 0 ]

R =

第 1 到 10 列

 1     1     2     2     7     7     7     7     5     5

第11到第16列

 5     5     9     9     9     9

性能：

a = repmat([ 1 0 2 0 7 7 7 0 5 0 0 0 9 ] ,1,10000); %//Double of 130,000
Arrayfun Method : Elapsed time is 6.840973 seconds.
AccumArray Method : Elapsed time is 2.097432 seconds.

- GameOfThrows

这与简单的for循环相比，在性能时间方面如何呢？arrayfun并不算向量化。有趣的是，进行比较，因为我不知道它是否比循环更优越，因为OP正在使用Octave，并且没有获得JIT的好处。但是比较必须在Octave中完成。 - Dan

1

我认为可以使用accumarray和cumsum的结合完成此操作。让我更新一下。 - GameOfThrows

7

我认为这是一种矢量化的解决方案。可适用于您的示例：

V = [1 0 2 0 7 7 7 0 5 0 0 0 9]
%// This is where the numbers you will repeat lie. You have to cast to a double otherwise later when you try assign numbers to it it caps them at logical 1s
d = double(diff([0,V])>0)
%// find(diff([0,~V])==-1) - find(diff([0,~V])==1) is the length of each zero cluster
d(find(d(2:end))+1) = find(diff([0,~V])==-1) - find(diff([0,~V])==1)
%// ~~V is the same as V ~= 0
V(cumsum(~~V+d)-1)

- Dan

2

另外，我在V的末尾填充了一个非零数字，如果不这样做，当V以0结尾时它是无法工作的；我想。 - GameOfThrows

2

@GameOfThrows 也是真的。在这种情况下，这将导致错误 find(diff([0,~V])==-1) - find(diff([0,~V])==1)。 - Dan

6

这里有另外一种解决方案，使用线性插值与前一个邻居查找。

我认为这种方法也很快，因为只需要查找和索引，没有计算：

in = [1 0 2 0 7 7 7 0 5 0 0 0 9]
mask = logical(in);
idx = 1:numel(in);
in(~mask) = interp1(idx(mask),in(mask),idx(~mask),'previous');
%// out = in

解释

您需要创建一个索引向量：

idx = 1:numel(in)  $// = 1 2 3 4 5 ...

并且还有一个逻辑掩码，可以遮盖所有非零值：

mask = logical(in);

这样，您可以获得插值的网格点 idx(mask) 和网格数据 in(mask)。查询点 idx(~mask) 是零数据的索引。然后通过 下一个前面的邻居 插值来计算查询数据 in(~mask)，因此它基本上查找网格中以前一个网格点为值的数值。这正是所需的。不幸的是，涉及的函数在所有可想象的情况下都有巨大的开销，因此它仍比Luis Mendo的答案慢，尽管没有涉及任何算术计算。

此外，可以稍微减少 interp1 的开销:

F = griddedInterpolant(idx(mask),in(mask),'previous');
in(~mask) = F(idx(~mask));

但是效果不是很明显。

in =   %// = out

     1     1     2     2     7     7     7     7     5     5     5     5     9

基准测试

0.699347403200000 %// thewaywewalk
1.329058123200000 %// GameOfThrows
0.408333643200000 %// LuisMendo
1.585014923200000 %// Dan

代码

function [t] = bench()
    in = repmat([ 1 0 2 0 7 7 7 0 5 0 0 0 9 ] ,1 ,100000);

    % functions to compare
    fcns = {
        @() thewaywewalk(in);
        @() GameOfThrows(in);
        @() LuisMendo(in);
        @() Dan(in);
    }; 

    % timeit
    t = zeros(4,1);
    for ii = 1:10;
        t = t + cellfun(@timeit, fcns);
    end
    format long
end

function in = thewaywewalk(in) 
    mask = logical(in);
    idx = 1:numel(in);
    in(~mask) = interp1(idx(mask),in(mask),idx(~mask),'previous');
end
function out = GameOfThrows(a) 
    pada = [a,888];
    b = pada(find(pada >0));
    bb = b(:,1:end-1);
    c = find (pada==0);
    d = find(pada>0);
    length = d(2:end) - (d(1:end-1));
    t = accumarray(cumsum([1,length])',1);
    out = bb(cumsum(t(1:end-1)));
end
function out = LuisMendo(in) 
    t = cumsum(in~=0);
    u = nonzeros(in);
    out = u(t).';
end
function out = Dan(V) 
    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);
end

- Robert Seifert

4

MATLAB R2016b中的新功能: fillmissing，它的作用正如问题描述的那样:

in = [ 1 0 2 0 7 7 7 0 5 0 0 0 9 ];
in(in==0) = NaN;
out = fillmissing(in,'previous');

[在这个重复的问题中发现了这个新功能]。

- Cris Luengo

2

向量运算通常假定各个项之间相互独立。如果您对先前的某个项有依赖关系，则循环是最好的方法。

关于Matlab的一些额外背景知识：在Matlab中，操作通常更快，并不是因为特定的向量操作，而是因为向量操作只是通过本地C++代码执行循环，而不是通过解释器执行。

- Scott M.

但是输入向量在开头给出，每次更新不依赖于先前的更新。因此从技术上讲，您应该能够在没有循环的情况下完成这个任务。 - GameOfThrows

3

这更像是一条评论而不是答案。此外，就MATLAB的定义而言，这个问题可以进行向量化处理。 - Dan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Luis Mendo · Accepted Answer

以下简单的方法可以满足您的需求，并且可能非常快速：

in = [1 0 2 0 7 7 7 0 5 0 0 0 9];
t = cumsum(in~=0);
u = nonzeros(in);
out = u(t).';