4 ms·
It is nice to see benchmarks of elementary algorithms, but none of these is new. Benchmarking would be more convincing if more distributions were used. For exam
by utopcell 6y ago
It is nice to see benchmarks of elementary algorithms, but none of these is new. Benchmarking would be more convincing if more distributions were used. For example, we know that interpolated search is O(lglgn) for uniform distributions that are used here, but can be linear in pathological cases.
- michaelmior 6y agoIt would be interesting to see an analysis of interpolated search with other known but non-uniform distributions.
- klyrs 6y agoExponentially distributed data is a great example of that. It's fun that the author picks 32-bit ints; I suspect that you just don't have enough dynamic range to really hobble interpolated search.