I think the fact that binary searches play into both the Lemire-Fenn algorithm and the binary-search algorithm is causing some confusion. Remember that the original Lemire algorithm, with its simple linear search and worst-case O(windowSize) per sample time, *still* manages O(1) per sample over any block of size larger than windowSize, and will thus outperform the binary search algorithm in terms of total complexity.
Understanding why that is the case --- IE, why the O(windowSize) wedge search can outperform the O(log2(windowSize)) heap search --- is strictly prerequisite to understanding why the Lemire-Fenn algorithm is more scalable than the binary search. It boils down to the fact that the actual number of comparisons performed in the wedge search is proportional to how many items are being removed from the wedge --- and each of those is less work we'll need to do next time. I believe the worst case for processing N samples with windowSize R is roughly O(N+R) for the original Lemire algorithm---because in the worst case we'll have to prune that many samples. As N approaches infinity, (N+R)/N approaches our amortized complexity: 1. The trick of the Lemire-Fenn algorithm is that it behaves as the Lemire algorithm, but caps the per-sample complexity by switching over to binary search just as the linear search surpasses O(log2(windowSize)) steps. This change reduces the complexity class for sample-by-sample processing without increasing the complexity in any case. – Evan Balster creator of imitone <http://imitone.com> On Sat, Sep 3, 2016 at 11:05 PM, Ross Bencina <rossb-li...@audiomulch.com> wrote: > On 4/09/2016 1:42 PM, robert bristow-johnson wrote: > >> i think the worst case ain't gonna be too much better than >> O(log2(windowSize)) per sample even with amortization over the block. >> > > You can think that if you like, but I don't think the worst case is that > bad. I have given examples. If you would like to provide a counter-example, > feel free. But first you probably need to understand the algorithm well > enough to implement it. > > I'm exiting this discussion now. Talking in vague terms isn't getting us > anywhere. Much as I would like to, I don't have time to write a new > implementation and a paper to convince you. > > Sorry, > > > 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
