Right aren't monotonic signals the worst case here? Or maybe not, since they're worst for one wedge, but best for the other?
Ethan D On Fri, Sep 2, 2016 at 10:12 AM, Evan Balster <e...@imitone.com> 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]. > > - If two equal samples are encountered, the algorithm can forget about the > older of them. > > It has been very helpful for my purposes to visualize the algorithm thus: > Imagine drawing lines rightward from all points on the signal. Those > which extend to the present time without intersecting other parts of the > signal form the minimum and maximum wedge. The newest sample, and only the > newest sample, exists in both wedges. > > [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. > > – Evan Balster > creator of imitone <http://imitone.com> > > On Fri, Sep 2, 2016 at 1:50 AM, Ross Bencina <rossb-li...@audiomulch.com> > wrote: > >> On 2/09/2016 4:37 PM, Ross Bencina wrote: >> >>> When the first difference is positive, the history is trimmed. This is >>> the only time any kind of O(N) or O(log2(N)) operation is performed. >>> First difference positive implies that a new local maximum is achieved: >>> in this case, all of the most recent history samples that are less than >>> the new maximum are trimmed. >>> >> >> Correction: >> >> [The new local maximum dominates all >>> history up to the most recent *history sample* that exceeds it, which is >>> retained.] >>> >> >> I had said "most recent local maximum" but the history contains a >> monotonic non-increasing sequence. >> >> Ross. >> >> _______________________________________________ >> 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
