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
