Path: news.mathworks.com!not-for-mail
From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: Re: vectorize finding upper envelope of vector
Date: Fri, 14 Mar 2008 15:47:01 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 90
Message-ID: <fre6ll$p28$1@fred.mathworks.com>
References: <frbrrt$n43$1@fred.mathworks.com> <frcc2m$h6i$1@fred.mathworks.com>
Reply-To: <HIDDEN>
NNTP-Posting-Host: webapp-05-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1205509621 25672 172.30.248.35 (14 Mar 2008 15:47:01 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Fri, 14 Mar 2008 15:47:01 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 870065
Xref: news.mathworks.com comp.soft-sys.matlab:457261



"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid>
wrote in message <frcc2m$h6i$1@fred.mathworks.com>...
> "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
> 
> 

A one-line vectorized cumulative maximum function:

  a = [2 3 4 2 7 5 8] % row vector
  CMA = max(triu(toeplitz(a)))

  % -> CMA =  2  3  4  4  7   7   8

which, however(!), will create an intermediate (numel(A).^2)
matrix that may cause memory troubles for long vectors.

SLIDEFUN on the File Exchange may be of interest to you as
well (shameful self promotion ...).

hth
Jos