---------------------------- Original Message ----------------------------
Subject: Re: [music-dsp] efficient running max algorithm
From: "Ethan Fenn" <et...@polyspectral.com>
Date: Wed, July 20, 2016 10:27 am
To: music-dsp@music.columbia.edu
--------------------------------------------------------------------------
> Of course, for processing n samples, something that is O(n) is going to
> eventually beat something that's O(n*log(w)), for big enough w.
i am skeptical of the claim. �at least for worst case. �if w = 2^30, i would
think the computational cost O(.) will have an increasing function of w in the
expression.
> FWIW if it's important to have
O(log(w)) worst case per sample, I think you
> can adapt the method of the paper to achieve this while keeping the O(1)
> average.
>
for real-time processing (that's how i think of a "running" max) the worst case
timing is what one has to worry about. �at least to prevent an unexpected
hiccup.
now, if the worst case *average* can be contained, then processing samples in
blocks can take advantage of
that averaging. �so if we process samples in, say, 32 or 64 sample blocks, and
the *worst case* timing of this can be guaranteed to beat the O(log2(w)), then
the alg has value. �but if it cannot be guaranteed to do that, it does not for
a real-time context.
> Instead of a linear
search back through the maxima, do a linear search for
> log2(w) samples and, failing that, switch to binary search. This is
> O(log(w)) worst case, but I think it would keep the property of O(1)
> comparisons per sample. I believe the upper bound would now be 4
> comparisons per sample rather than 3. I'd have to think more about it to be
> sure.
�
because i am having trouble understanding *exactly* the alg, i would still
appreciate a snippet of code.
i will bet, that given a snippet of code, i can think of a signal that will
push the computational cost into the worst case which will be worse than
O(log2(w)).
--
r b-j � � � � � � � � � � �r...@audioimagination.com
"Imagination is more important than knowledge."
_______________________________________________
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp
