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 <http://imitone.com> 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" <e...@imitone.com> > 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 <http://imitone.com> > > > > On Thu, Jul 21, 2016 at 10:16 AM, Evan Balster <e...@imitone.com> 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 <http://imitone.com> > >> > >> On Thu, Jul 21, 2016 at 7:40 AM, Ethan Fenn <et...@polyspectral.com> > >> 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 <e...@imitone.com> > 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 <http://imitone.com> > > >>>> > >>>> 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 > > > _______________________________________________ > 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
