Re: [music-dsp] efficient running max algorithm

[Evan Balster]

Hey, Robert ---

Check out Lemire's paper, or my summary in the third message in this
thread.  When computing both minimum and maximum over a range of size R and
over N samples, the total computational complexity is bounded by O(N) ---
that is, amortized constant time per sample --- while the worst case for
any sample is O(log2(R)) --- or just O(R) in Lemire's original algorithm.

If you do a binary search every sample, you get O(log2(R)) worst case per
sample but you lose the amortized constant time characteristic.  To keep
that, you need to use a hybrid search as proposed by Ethan here and
implemented in my code.

High frequencies won't really make a difference.  In any case the combined
sizes of the two wedges will never exceed R+1, and will typically be much
smaller.  Feel free to customize the unit test in the GitHub to your
satisfaction if you're doubtful.

– Evan Balster
creator of imitone 

On Thu, Sep 1, 2016 at 11:52 PM, robert bristow-johnson <
r...@audioimagination.com> wrote:

>
>
> i think i understand the algorithm.  let's assume running max.  you will,
> for each wedge, keep a record of the height and location of the maximum.
>
> and for only two wedges, the wedge that is falling of the edge of the
> delay buffer and the new wedge being formed from the new incoming samples,
> only on those two wedges you need to monitor and update on a
> sample-by-sample basis. as a wedge is created on the front end and as it
> falls offa the back end, you will have to update the value and location of
> the maxima of each of those two wedges.
>
> each time the first derivative (the difference between the most current
> two samples) crosses zero from a positive first difference to a negative
> first difference (which is when you have a maximum), you have to record a
> new wedge, right?
>
> and then you do a binary max tree for the entire set of wedge maxima?  is
> that how it works?
>
> the latter part is O(log2(N)) worst case.  are you expecting a computation
> savings over the straight binary search tree because the number of wedges
> are expected to be a lot less than the buffer length?
>
> if it's a really high frequency signal, you'll have lotsa wedges.  then i
> think there won't be that much difference between the O(log2(N)) worst case
> of this Lemire thing and the O(log2(N)) worst case of a straight binary
> tree.  and the latter has **very** simple self-contained code (which was
> previously posted).
>
> i just wanna know, most specifically, what is the expectation of gain of
> speed (or reduction of execution time) of this Lemire alg over the simpler
> binary tree alg.  it doesn't seem to me to be a lot better for memory
> requirements.
>
>
> --
>
> r b-j  r...@audioimagination.com
>
> "Imagination is more important than knowledge."
>
>
>
>  Original Message 
> Subject: Re: [music-dsp] efficient running max algorithm
> From: "Evan Balster" 
> Date: Fri, September 2, 2016 12:12 am
> To: music-dsp@music.columbia.edu
> --
>
> > Hello, all ---
> >
> > Reviving this topic to mention I've created an STL-compatible header
> > implementing what I'm calling the "Lemire-Fenn" algorithm for rolling
> > minimum and maximum:
> >
> > https://github.com/EvanBalster/STL_mono_wedge
> >
> > This was a little pet project I undertook today to familiarize myself
> with
> > Github; the algorithm itself is about ten lines of code, but I've
> > documented it obsessively and run it through a series of unit tests. It's
> > compatible with std::vector, std::deque, and (I imagine) any
> STL-compliant
> > ringbuffer class exposing random-access iterators.
> >
> > Feel free to share any feedback or thoughts about this.
> >
> > – Evan Balster
> > creator of imitone 
> >
> > On Thu, Jul 21, 2016 at 10:16 AM, Evan Balster  wrote:
> >
> >> Ahh, smart! Thanks for the insight; I understand now.
> >>
> >> It occurs to me that you could slightly tighten the bound on per-sample
> >> work, because it's not necessary to include the elements of the linear
> >> search in the binary one. The worst-case would then be O(J) per sample,
> >> where J=log2(w-J). But this is a very marginal improvement and it's
> >> difficult to write out the bound in a clearer way.
> >>
> >> – Evan Balster
> >> creator of imitone 
> >>
> >> On Thu, Jul 21, 2016 at 7:40 AM, Ethan Fenn 
> >> wrote:
> >>
> >>> Yeah, with a binary search, you're doing O(log(w)) work, but you might
> >>> not end up discarding any samples. With the paper's linear search, you
> >>> might do O(w) work, but only if you end up discarding O(w) samples.
> So, it
> >>> turns out to be worth it, as long as you can tolerate the spike.
> >>>
> >>> The thinking with the partial linear search is sure, let's spend
> >>> O(log(w)) time 

Re: [music-dsp] efficient running max algorithm

[robert bristow-johnson]

�
i think i understand the algorithm. �let's assume running max. �you will, for 
each wedge, keep a record of the height and location of the maximum.
and for only two wedges, the wedge that is falling of the edge of the delay 
buffer and the new wedge being formed from
the new incoming samples, only on those two wedges you need to monitor and 
update on a sample-by-sample basis. as a wedge is created on the front end and 
as it falls offa the back end, you will have to update the value and location 
of the maxima of each of those two wedges.
each time the first
derivative (the difference between the most current two samples) crosses zero 
from a positive first difference to a negative first difference (which is when 
you have a maximum), you have to record a new wedge, right?
and then you do a binary max tree for the entire set of wedge maxima?
�is that how it works?
the latter part is O(log2(N)) worst case. �are you expecting a computation 
savings over the straight binary search tree because the number of wedges are 
expected to be a lot less than the buffer length?
if it's a really high frequency signal, you'll have
lotsa wedges. �then i think there won't be that much difference between 
the�O(log2(N)) worst case of this Lemire thing and the�O(log2(N)) worst case of 
a straight binary tree. �and the latter has **very** simple self-contained 
code�(which was previously posted).
i just
wanna know, most specifically, what is the expectation of gain of speed (or 
reduction of execution time) of this Lemire alg over the simpler binary tree 
alg. �it doesn't seem to me to be a lot better for memory requirements.

--
r b-j � � � � � � � � � � �r...@audioimagination.com
"Imagination is more important than knowledge."




 Original Message 

Subject: Re: [music-dsp] efficient running max algorithm

From: "Evan Balster" 

Date: Fri, September 2, 2016 12:12 am

To: music-dsp@music.columbia.edu

--



> Hello, all ---

>

> Reviving this topic to mention I've created an STL-compatible header

> implementing what I'm calling the "Lemire-Fenn" algorithm for rolling

> minimum and maximum:

>

> https://github.com/EvanBalster/STL_mono_wedge

>

> This was a little pet project I undertook today to familiarize myself with

> Github; the algorithm itself is about ten lines of code, but I've

> documented it obsessively and run it through a series of unit tests. It's

> compatible with std::vector, std::deque, and (I imagine) any STL-compliant

> ringbuffer class exposing random-access iterators.

>

> Feel free to share any feedback or thoughts about this.

>

>  Evan Balster

> creator of imitone 

>

> On Thu, Jul 21, 2016 at 10:16 AM, Evan Balster  wrote:

>

>> Ahh, smart! Thanks for the insight; I understand now.

>>

>> It occurs to me that you could slightly tighten the bound on per-sample

>> work, because it's not necessary to include the elements of the linear

>> search in the binary one. The worst-case would then be O(J) per sample,

>> where J=log2(w-J). But this is a very marginal improvement and it's

>> difficult to write out the bound in a clearer way.

>>

>>  Evan Balster

>> creator of imitone 

>>

>> On Thu, Jul 21, 2016 at 7:40 AM, Ethan Fenn 

>> wrote:

>>

>>> Yeah, with a binary search, you're doing O(log(w)) work, but you might

>>> not end up discarding any samples. With the paper's linear search, you

>>> might do O(w) work, but only if you end up discarding O(w) samples. So, it

>>> turns out to be worth it, as long as you can tolerate the spike.

>>>

>>> The thinking with the partial linear search is sure, let's spend

>>> O(log(w)) time doing a binary search, but only if we first confirm we'll be

>>> discarding at least O(log(w)) samples.

>>>

>>> -Ethan

>>>

>>>

>>>

>>>

>>> On Wed, Jul 20, 2016 at 6:37 PM, Evan Balster  wrote:

>>>

 Ethan ---



 If we use only a binary search in the discard step, isn't the amortized

 complexity still O(N)? I suppose not... We'd be doing a log2(w) search

 every sample in the worst case where a monotonic decrease occurs.



 I'll have to look over the paper to get a better understanding, but

 would be very interested to hear your thought process with the partial

 linear search.



  Evan Balster

 creator of imitone 



 On Wed, Jul 20, 2016 at 1:23 PM, Dan Gillespie <

 dgilles...@cosineaudio.com> wrote:



> Regarding the Lemire paper his code is provided here:

> https://github.com/lemire/runningmaxmin

>

> It's been a while since I've read the paper, but iirc it reports fast

> average O(.), not worst case. Specifically it's good if the signal has few

> changes in direction, but the 

Re: [music-dsp] efficient running max algorithm

[Evan Balster]

Hello, all ---

Reviving this topic to mention I've created an STL-compatible header
implementing what I'm calling the "Lemire-Fenn" algorithm for rolling
minimum and maximum:

https://github.com/EvanBalster/STL_mono_wedge

This was a little pet project I undertook today to familiarize myself with
Github; the algorithm itself is about ten lines of code, but I've
documented it obsessively and run it through a series of unit tests.  It's
compatible with std::vector, std::deque, and (I imagine) any STL-compliant
ringbuffer class exposing random-access iterators.

Feel free to share any feedback or thoughts about this.

– Evan Balster
creator of imitone 

On Thu, Jul 21, 2016 at 10:16 AM, Evan Balster  wrote:

> Ahh, smart!  Thanks for the insight; I understand now.
>
> It occurs to me that you could slightly tighten the bound on per-sample
> work, because it's not necessary to include the elements of the linear
> search in the binary one.  The worst-case would then be O(J) per sample,
> where J=log2(w-J).  But this is a very marginal improvement and it's
> difficult to write out the bound in a clearer way.
>
> – Evan Balster
> creator of imitone 
>
> On Thu, Jul 21, 2016 at 7:40 AM, Ethan Fenn 
> wrote:
>
>> Yeah, with a binary search, you're doing O(log(w)) work, but you might
>> not end up discarding any samples. With the paper's linear search, you
>> might do O(w) work, but only if you end up discarding O(w) samples. So, it
>> turns out to be worth it, as long as you can tolerate the spike.
>>
>> The thinking with the partial linear search is sure, let's spend
>> O(log(w)) time doing a binary search, but only if we first confirm we'll be
>> discarding at least O(log(w)) samples.
>>
>> -Ethan
>>
>>
>>
>>
>> On Wed, Jul 20, 2016 at 6:37 PM, Evan Balster  wrote:
>>
>>> Ethan ---
>>>
>>> If we use only a binary search in the discard step, isn't the amortized
>>> complexity still O(N)?  I suppose not...  We'd be doing a log2(w) search
>>> every sample in the worst case where a monotonic decrease occurs.
>>>
>>> I'll have to look over the paper to get a better understanding, but
>>> would be very interested to hear your thought process with the partial
>>> linear search.
>>>
>>> – Evan Balster
>>> creator of imitone 
>>>
>>> On Wed, Jul 20, 2016 at 1:23 PM, Dan Gillespie <
>>> dgilles...@cosineaudio.com> wrote:
>>>
 Regarding the Lemire paper his code is provided here:
 https://github.com/lemire/runningmaxmin

 It's been a while since I've read the paper, but iirc it reports fast
 average O(.), not worst case.  Specifically it's good if the signal has few
 changes in direction, but the worst case is not better than other
 algorithms.

 Dan Gillespie

 ___
 dupswapdrop: music-dsp mailing list
 music-dsp@music.columbia.edu
 https://lists.columbia.edu/mailman/listinfo/music-dsp


>>>
>>> ___
>>> dupswapdrop: music-dsp mailing list
>>> music-dsp@music.columbia.edu
>>> https://lists.columbia.edu/mailman/listinfo/music-dsp
>>>
>>
>>
>> ___
>> dupswapdrop: music-dsp mailing list
>> music-dsp@music.columbia.edu
>> https://lists.columbia.edu/mailman/listinfo/music-dsp
>>
>
>
___
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp