4 ms·
Good for sorting hashes.
by Paperweight 7y ago
Good for sorting hashes.
- anilakar 7y agoAny good hashing function would already be uniformly distributed, right? In that case, using this algorithm over traditional ones makes little sense.
- adwn 7y ago> Any good hashing function would already be uniformly distributed, right? In that case, using this algorithm over traditional ones makes little sense. I think you're misunderstanding Paperweight's post and/or the idea behind flashsort. Hashes are uniformly distributed, hence you can use flashsort (instead of mergesort, quicksort, etc.) and get a time complexity of O(n) instead of O(N*log(N)).
- anilakar 7y agoMany sorting algorithms that work on uniform distributions do exist and they often use plain old insertion sort under the hood. As I see it, Flashsort only exploits that by knowing the CDF beforehand, you can turn the data piecewise linear and then use more classic methods on that.
- gorset 7y agoAn array of sorted hashes is also nice combined with interpolation search [0] (or hinted binary search) which can give a nice speedup compared to "naive" binary search. [0] https://en.wikipedia.org/wiki/Interpolation_search https://en.wikipedia.org/wiki/Interpolation_search
- martin_a 7y agoWhy would you want to sort hashes? Not sure I see the application for hashes here, but that's totally my fault.
- kyrieeschaton 7y agoTo have a duplicable traversal order.