---------------------------- Original Message ----------------------------
Subject: Re: [music-dsp] efficient running max algorithm
From: "Ross Bencina" <rossb-li...@audiomulch.com>
Date: Fri, September 2, 2016 10:19 pm
To: music-dsp@music.columbia.edu
--------------------------------------------------------------------------
> On 3/09/2016 3:12 AM, Evan Balster wrote:
>> Just a few clarifications:
>>
>> - Local maxima and first difference don't really matter. The maximum
>> wedge describes global maxima for all intervals [t-x, t], where
>> x=[R-1..0].can you clarify N vs. R? �is N the length of the delay line and
>> for each new input
sample we want the output to be the max value for the most current N input
samples?� �y[n] = max{ x[n], x[n-1], x[n-2], ... x[n-N+1] } ?and you are
processing R samples at a time? �what difference does R make? �it is not a
specification of the running max delay buffer.>�Your STL version makes
the�algorithm clearer.this, i think, spells out the difference in perspectives
between C and C++ coders.my (c) 1986 Stroustrup book doesn't really say a thing
about STL and Vectors. �and in discussing iterators, says nothing about
push_back() and the like. �from online i can get an idea,
but it seems to me to be a LIFO stack, not a FIFO buffer. �so a sample value
gets pushed onto this thing and pop_back() pops it off, but how does the oldest
sample get pushed off the front? �what makes this vector a circular FIFO
thingie?C++ sucks. �and for someone not competent in C++ STL, the code is
opaque.that said, the
"10 lines of code" is deceptive. �it's 10 lines of code with function calls.
�you gotta count the cost of the function calls. �again, the binary tree code
in C (i posted July 18) has *no* function calls (except for a single malloc()
in the initialization) and has about 11
lines of code, not counting blank lines or lines with just a curly brace. �no
calls to any method that has who knows what for an overhead.now, Ross, this is
Evan's
diagram (from earlier today), but maybe you can help me:
[image: Inline image 3]
http://interactopia.com/archive/images/lemire_algorithm.png
> The algorithm can safely forget anything in grey because it has been
> "shadowed" by newer maximum or minimum values.
�what is not shown on the diagram is what happens when the current running max
value expires (or falls off the edge of the delay buffer)? �when the current max
value falls offa the edge, what must you do to find the new maximum over the
past N samples?you would have to be riding the slope down on the left side of
the peak that
just fell offa the edge and then how do you compare that value to any peaks
(that are lower for the moment) that have not yet expired? �they have to be
other wedges, right? �with their own record of height and location, right? �the
only thing shown on that diagram is what happens when
new maxima come into the delay line on the left and the running max value
increases. �it does not show how it decreases and the running max must decrease
eventually.i
cannot see how this strategy works without keeping a record of *every* local
maxima. �both its value and its location. �that record would also be FIFO and
the size of that record would be large if there were a lotta peaks (like a high
frequency signal), but each entry would be
chronologically placed.any local maximum between the current running max and
the "runner up" (which is more current) can be ignored. �perhaps this means
that you only need to note where the current running max is (both location and
value) and the runner-up that is more current. �when the current max falls offa
the edge on the right, you have to ride the left slope of that peak (which is
at the maximum delay location) down until it's the value
of the runner up and then all samples between the new running max and the end
of the delay buffer can be ignored. �but here is the question, when the runner
up is promoted to the running max, how is the *new* runner up found? �that
could be anywhere between the buffer input (on the left
side) and the new running max. �if you are not already performing a binary tree
on that , i cannot see how finding the new runner up is cheap, unless you have
a record of every local max between the buffer input (on the left side) and the
new running max. �and each time a new local max is
detected, you have to do the O(log2(something)) binary tree thing.
--
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
