Thread Subject: Fast vector filling

Hi all

I have a bit of a problem which has somewhat stumped me. Let's say I
have a vector like

[1 2 0 0 0 -3 0 0 0 1 0 0 0 5 0 7 0 0 0 3 0 2]
(approximately 50% zeros)

What is a fast way to turn it into
[1 2 2 2 2 -3 -3 -3 -3 1 1 1 1 5 5 7 7 7 7 3 3 2]

i.e. all zeros are replaced with the nearest nonzero to the left? This
is easy to do with a loop, but when your vectors have O(1e6)
elements, it's not so much fun ... however, I wouldn't be surprised if
there's a convenient one liner.

Any thoughts would be appreciated,

Richard Brown

Richard Brown <rgbrown@gmail.com> wrote in message
<9b9c9f5c-e89e-41e7-9ef0-
28fe3b2340b0@q24g2000prf.googlegroups.com>...
> Hi all
>
> I have a bit of a problem which has somewhat stumped me.
Let's say I
> have a vector like
>
> [1 2 0 0 0 -3 0 0 0 1 0 0 0 5 0 7 0 0 0 3 0 2]
> (approximately 50% zeros)
>
> What is a fast way to turn it into
> [1 2 2 2 2 -3 -3 -3 -3 1 1 1 1 5 5 7 7 7 7 3 3 2]
>
> i.e. all zeros are replaced with the nearest nonzero to
the left? This
> is easy to do with a loop, but when your vectors have O
(1e6)
> elements, it's not so much fun ... however, I wouldn't be
surprised if
> there's a convenient one liner.
>
> Any thoughts would be appreciated,
>
> Richard Brown
>

Assuming the first element of your vector "a" is non-zero,
this will do it:

  I = find(a(1:end-1)~=0 & a(2:end)==0);
  i = cumsum(histc(I,[0 find(a==0)]));
  a(a==0) = a(I(i(1:end-1)));

For a sample with 1e6 elements and 50% zeros, it ran in
about 0.3 seconds.

Richard Brown <rgbrown@gmail.com> wrote in message
<9b9c9f5c-e89e-41e7-9ef0-
28fe3b2340b0@q24g2000prf.googlegroups.com>...
> Hi all
>
> I have a bit of a problem which has somewhat stumped me.
Let's say I
> have a vector like
>
> [1 2 0 0 0 -3 0 0 0 1 0 0 0 5 0 7 0 0 0 3 0 2]
> (approximately 50% zeros)
>
> What is a fast way to turn it into
> [1 2 2 2 2 -3 -3 -3 -3 1 1 1 1 5 5 7 7 7 7 3 3 2]
>
> i.e. all zeros are replaced with the nearest nonzero to
the left? This
> is easy to do with a loop, but when your vectors have O
(1e6)
> elements, it's not so much fun ... however, I wouldn't be
surprised if
> there's a convenient one liner.
>
> Any thoughts would be appreciated,
>
> Richard Brown
>

Assuming the first element of your vector "a" is non-zero,
this will do it:

  I = find(a(1:end-1)~=0 & a(2:end)==0);
  i = cumsum(histc(I,[0 find(a==0)]));
  a(a==0) = a(I(i(1:end-1)));

For a sample with 1e6 elements and 50% zeros, it ran in
about 0.3 seconds.

Richard Brown <rgbrown@gmail.com> wrote in message
<9b9c9f5c-e89e-41e7-9ef0-28fe3b2340b0@q24g2000prf.googlegroups.com>...
> Hi all
>
> I have a bit of a problem which has somewhat stumped me.
Let's say I
> have a vector like
>
> [1 2 0 0 0 -3 0 0 0 1 0 0 0 5 0 7 0 0 0 3 0 2]
> (approximately 50% zeros)
>
> What is a fast way to turn it into
> [1 2 2 2 2 -3 -3 -3 -3 1 1 1 1 5 5 7 7 7 7 3 3 2]
>
> i.e. all zeros are replaced with the nearest nonzero to
the left? This
> is easy to do with a loop, but when your vectors have O(1e6)
> elements, it's not so much fun ... however, I wouldn't be
surprised if
> there's a convenient one liner.
>
> Any thoughts would be appreciated,
>
> Richard Brown
>


One of the faster solutions:

x = [0 1 0 0 4 0 2 3 0 0 0 8 0] ;
x2 = zeros(size(x)) ;
i = find(x) ;
x2(i(2:end)) = diff(x(i)) ;
x2 = cumsum(x2) + x(i(1)) ;
x2(1:i-1) = 0 ;


hth
Jos

"Jos ":
<SNIP down to nice solution

> One of the faster solutions:
> x = [0 1 0 0 4 0 2 3 0 0 0 8 0] ;
> x2 = zeros(size(x)) ;
> i = find(x) ;
> x2(i(2:end)) = diff(x(i)) ;
> x2 = cumsum(x2) + x(i(1)) ;
> x2(1:i-1) = 0 ;

one of the many(!) other solutions

% the data
     x=[0 -4 0 0 4 0 2 3 0 0 0 8 0];
% the engine
     xs=cumsum(x~=0);
     xo=x~=0;
     ib=x(xo);
     x(xo)=ib(xs(xo));
% the resulst
     x
% x = 0 -4 -4 -4 4 4 2 3 3 3 3 8 8

us

"us ":
<SNIP copy/pasted wrong history entries(!!!)...

one of the many(!) other solutions

% the data
     x=[0 -4 0 0 4 0 2 3 0 0 0 8 0];
% the engine
     xs=cumsum(x~=0);
     ib=x(x~=0); % <- correct!
     xo=xs~=0; % <- correct!
     x(xo)=ib(xs(xo));
% the resulst
     x
% x = 0 -4 -4 -4 4 4 2 3 3 3 3 8 8

sorry for this...
us

Richard Brown:
<SNIP timing three solutions...

the code below yields those numbers on a
wintel: ic2.2*2.4mhz/2g/winxp.sp2/r2007b

     'helper' [ 1.8138]
     'jos' [0.63897] % the winner!
     'us' [ 1.0522]

but: <helper> and <jos> come with some limitations (see
snippet...)

just for fun...
us

     v=rand(1,1000000);
     v(v>.3)=0;
     v(1)=1; % for <helper>
     nt=10;
% helper: solution does not take v(1)=0!
     tic;
for j=1:nt
     a=v;
     I = find(a(1:end-1)~=0 & a(2:end)==0);
     i = cumsum(histc(I,[0 find(a==0)]));
     a(a==0) = a(I(i(1:end-1)));
end
     t{1,1}=toc;
     r1=a;
% jos: solution does not take all(v==0)!
     tic;
for j=1:nt
     x=v;
     x2 = zeros(size(x)) ;
     i = find(x) ;
     x2(i(2:end)) = diff(x(i)) ;
     x2 = cumsum(x2) + x(i(1)) ;
     x2(1:i-1) = 0 ;
end
     t{2,1}=toc;
     r2=x2;
% us: takes all above <anomalies>
     tic
for j=1:nt
% the engine
     x=v;
     xo=x~=0;
     xs=cumsum(xo);
     ib=x(xo);
     xo=xs~=0;
     x(xo)=ib(xs(xo));
end
     t{3,1}=toc;
     r3=x;
     isequal(r1,r2,r3)
     disp([{'helper';'jos';'us'},t]);
% ans = 1

On May 13, 9:58 pm, "us " <u...@neurol.unizh.ch> wrote:
<SNIP>
> the code below yields those numbers on a
> wintel: ic2.2*2.4mhz/2g/winxp.sp2/r2007b
>
> 'helper' [ 1.8138]
> 'jos' [0.63897] % the winner!
> 'us' [ 1.0522]
</SNIP>

Thanks all for your responses and Urs for the comparison - I'll be
using Jos's method :). This thread is (yet) another example of how
much value CSSMers add to Matlab as a development tool.

Richard

Richard Brown <rgbrown@gmail.com> wrote in message
<3e22ea60-a0f8-4f91-a786-
aa76764038e5@t12g2000prg.googlegroups.com>...
> On May 13, 9:58 pm, "us " <u...@neurol.unizh.ch> wrote:
> <SNIP>
> > the code below yields those numbers on a
> > wintel: ic2.2*2.4mhz/2g/winxp.sp2/r2007b
> >
> > 'helper' [ 1.8138]
> > 'jos' [0.63897] % the winner!
> > 'us' [ 1.0522]
> </SNIP>
>
> Thanks all for your responses and Urs for the comparison -
 I'll be
> using Jos's method :). This thread is (yet) another
example of how
> much value CSSMers add to Matlab as a development tool.
>
> Richard


I have just posted my solution to the FEX. It can handle
multidimensional matrices, by operating on a specified
dimension. and all zeros, NaNs, Infs etc.

http://www.mathworks.com/matlabcentral/fileexchange/loadFile
.do?objectId=19906&objectType=FILE
(beware of line wraps)

Thanks, Richard, for the challenge!

Jos

On May 15, 8:00 am, "Jos " <DEL...@jasenDEL.nl> wrote:
> Richard Brown <rgbr...@gmail.com> wrote in message
>
> <3e22ea60-a0f8-4f91-a786-
> aa7676403...@t12g2000prg.googlegroups.com>...
>
>
>
> > On May 13, 9:58 pm, "us " <u...@neurol.unizh.ch> wrote:
> > <SNIP>
> > > the code below yields those numbers on a
> > > wintel: ic2.2*2.4mhz/2g/winxp.sp2/r2007b
>
> > > 'helper' [ 1.8138]
> > > 'jos' [0.63897] % the winner!
> > > 'us' [ 1.0522]
> > </SNIP>
>
> > Thanks all for your responses and Urs for the comparison -
> I'll be
> > using Jos's method :). This thread is (yet) another
> example of how
> > much value CSSMers add to Matlab as a development tool.
>
> > Richard
>
> I have just posted my solution to the FEX. It can handle
> multidimensional matrices, by operating on a specified
> dimension. and all zeros, NaNs, Infs etc.
>
> http://www.mathworks.com/matlabcentral/fileexchange/loadFile
> .do?objectId=19906&objectType=FILE
> (beware of line wraps)
>
> Thanks, Richard, for the challenge!
>
> Jos

Very nice!