Path: news.mathworks.com!not-for-mail
From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: Re: vectorize finding upper envelope of vector
Date: Thu, 13 Mar 2008 23:07:02 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 52
Message-ID: <frcc2m$h6i$1@fred.mathworks.com>
References: <frbrrt$n43$1@fred.mathworks.com>
Reply-To: <HIDDEN>
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 1205449622 17618 172.30.248.38 (13 Mar 2008 23:07:02 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Thu, 13 Mar 2008 23:07:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1187260
Xref: news.mathworks.com comp.soft-sys.matlab:457148



"ashipyard " <andrewshipyard@hush.com> wrote in message <frbrrt$n43
$1@fred.mathworks.com>...
> I hope someone can help me vectorize some code.
> 
> I have a vector a. I want to return the upper envelope of a,
> based on its original sort order.
> 
> E.g.
> 
> if a = [2 3 4 2 7 5 8]
> 
> I would want to return: [2 3 4 4 7 7 8].
> 
> Clearly this is very easy in a for loop.
> 
> for i=2:length(a)
>   if (a(i)<a(i-1))
>     a(i)=a(i-1);
>   end
> end
> 
> However, I can't think of an easy way to vectorize this.
> Looping is slow when the length of a is large.
> 
> Thank you for your help
----------
  What you are asking for is a "cumulative" maximum function.  I have seen 
this question arise many times on this newsgroup and each time no-one 
seems to have been able to come up with a good vectorized solution.  
Furthermore, even if someone did manage to stumble across some magical 
combination of such things as cumsums, diffs, and whatnot, that would 
accomplish the task, it is highly likely that, at least on the newer matlab 
versions, it would take far longer to execute than doing it your for-loop way.

  I strongly suspect that it would be comparatively easy for Mathworks, if they 
thought it was worthwhile, to devise a fast cumulative maximum function at 
the low level coding which is available to them and which would execute with 
the same speed as 'sum', 'find', etc., but until and unless they do, you may 
have to be content with the for-loop method.  There is no disgrace in using a 
for-loop.  It is a highly essential construct in the matlab language.

  Remember, each of the so-called vectorized operations is accomplished in 
the same way it would be done in a for-loop or the like, one step at a time.  
To do 'sum', the computer adds the first number to the second, then adds 
their sum to the third, then that sum to the fourth one, etc., just as a for-loop 
would do.  However, doing this at low level coding can eliminate a certain 
amount of overhead that is associated with for-loop indexing executed at a 
higher language level.

Roger Stafford