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
