[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: cumulative maximum (was: 'for' loop vectorization)
From: |
Hermann Schwarting |
Subject: |
Re: cumulative maximum (was: 'for' loop vectorization) |
Date: |
Wed, 7 Nov 2007 11:37:31 +0100 |
User-agent: |
KMail/1.9.7 |
Am Dienstag, 23. Oktober 2007 schrieb Jordi Gutiérrez Hermoso:
> On 23/10/2007, Hermann Schwarting <address@hidden> wrote:
> > The more I think about it, it looks like I can't vectorize this.
> > It's a bit similar to a cumulative maximum, which can't be
> > vectorized either, I think.
>
> It can be, but my vectorisation runs slower than the unvectorised
> code. :-(
>
> a = max(triu(repmat(a(:),1,length(a))))
>
> The triu call is the bottleneck, it seems, which mystifies me.
I was wrong. Here is a recursive version of cummax that needs O(log2
n) recursions and is faster than a naïve implementation. The use of
triu() is prohibitive if the input is a large vector, because of
memory consumption.
function X = cummax( X )
n = length(X);
if n == 2,
X(2) = max(X);
elseif n > 2,
X(2:2:n) = cummax( max( X(1:2:n-1), X(2:2:n) ));
X(3:2:n) = max( X(3:2:n), X(2:2:n-1) );
end
Kind regards,
Hermann
- Re: cumulative maximum (was: 'for' loop vectorization),
Hermann Schwarting <=