Path: news.mathworks.com!not-for-mail
From: "William Dampier" <walldo2@gmail.com>
Newsgroups: comp.soft-sys.matlab
Subject: Re: finding consecutive numbers (runs)
Date: Thu, 13 Dec 2007 06:53:44 +0000 (UTC)
Organization: Drexel University
Lines: 77
Message-ID: <fjqkto$9mc$1@fred.mathworks.com>
References: <fjp9pj$p8g$1@fred.mathworks.com> <fjpihi$p2j$1@fred.mathworks.com> <fjplk2$fgm$1@fred.mathworks.com> <fjqfa3$ce4$1@fred.mathworks.com>
Reply-To: "William Dampier" <walldo2@gmail.com>
NNTP-Posting-Host: webapp-03-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1197528824 9932 172.30.248.38 (13 Dec 2007 06:53:44 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Thu, 13 Dec 2007 06:53:44 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1084889
Xref: news.mathworks.com comp.soft-sys.matlab:442278


>   William, it has occurred to me that the 'fliplr'
operations are not really 
> needed at all in the above processing if the appropriate
steps are taken.  
> Besides these two 'fliplr' operations, one 'diff' and one
'find' operation can 
> also be eliminated.  Consequently you may find that,
hopefully, a little 
> execution time will be saved.
> 
>   Again, if x is the m by n array whose rows are to be
processed in the 
> specified manner, then do this:
> 
>  m = size(x,1);
>  y = [reshape([zeros(1,m);x.'],[],1);0];
>  z = y;
>  p = find(~y);
>  d = 1-diff(p);
>  y(p) = [0;d];
>  y = reshape(cumsum(y(1:end-1)),[],m).';
>  y(:,1) = [];
>  z(p) = [d;0];
>  z = reshape(cumsum(-z(1:end-1)),[],m).';
>  z(:,end) = [];
> 
> The y array will then be the above-mentioned 'desired2'
array, and z will be 
> the 'desired1' array, both of size m by n.
> 
> Roger Stafford
> 


Yup that works:
Times for processing the whole matrix:

for-loop (with pre-allocation): ~50 seconds do both
vectorized with fliplr: ~15 seconds
new vectorized: ~10 seconds 

A 5-second improvement is still significant since this will
be calculated thousands of times.

Since the input matrix is 5188x9110 and it is ~50-60% full
which makes the temp array p is ~27,100,000 of doubles.

The 'reshape' statement is the only bottleneck.  I separated
out the cumsum statement just to check which was the
offending statement.

I've been checking the 'bsxfun' since it might let me avoid
the temp arrays.

On a similar note I've noticed drastically different
performance based on whether the function is implemented as
a stand-alone m-file as opposed to a sub-function.

Stand-alone times:
for-loop (with pre-allocation): ~50 seconds do both
vectorized with fliplr: ~15 seconds
new vectorized: ~10 seconds 

subfunction times:
for-loop (with pre-allocation): ~55 seconds do both
vectorized with fliplr: ~120 seconds
new vectorized: ~150 seconds 

The choice of implementation is obvious but I'm not sure of
the reason.  I would have expected the opposite results.  If
you have any idea why this would happen it would help
satisfy my intellectual curiosity.

Thanks
Will