The unreasonable effectiveness of modern sort algorithms
1–10 of 62 posts
Re: The unreasonable effectiveness of modern sort algorithms
#2[deleted]
Re: The unreasonable effectiveness of modern sort algorithms
#3The efforts of developing better sorting algorithms like driftsort/ipnsort and better hash functions like foldhash make my life as developer so much simpler. No matter how clever I try to be, most often just using foldhash hashmap or a sort_unstable is the fastest option
Re: The unreasonable effectiveness of modern sort algorithms
#4Efficiency, not effectiveness. They are all effective in the sense that they produce sorted results. Even the non-modern sort algorithms are effective in the sense that the results are correct. This should be about the efficiency with which they do it, right?
Re: The unreasonable effectiveness of modern sort algorithms
#5Double jaw-drop. First when the (dynamic) match was slower than the hash map, second when sort_unstable was faster than the hash map!
Cool article. It's clear that all my theoretical algorithm-knowledge comes short when faced with real CPUs.
Re: The unreasonable effectiveness of modern sort algorithms
#6Efficiency, not effectiveness. They are all effective in the sense that they produce sorted results. Even the non-modern sort algorithms are effective in the sense that the results are correct. This should be about the efficiency with which they do it, right?
Agreed. Effectiveness would imply that some algorithms are more likely to sort the list correctly than others, or they sort a higher percentage of elements. Efficiency is about factors external to the correctness
Re: The unreasonable effectiveness of modern sort algorithms
#7Isn't this just another case of premature optimization? Shouldn't you be adjusting sorting algorithms only when customer complains?
Re: The unreasonable effectiveness of modern sort algorithms
#8I find in practice that if the sorting process is too slow, you should begin thinking about different ways to attack the problem. Maintaining a total global order of things tends to only get more expensive over time as the scope of your idea/product/business expands. The computational complexity of the sort algorithm is irrelevant once we get into memory utilization.
This is why we have things like tournament selection. Randomly sampling from the population and running tournaments is way more scalable than scanning and ordering a global list each iteration. You can maintain things like an ELO score with very narrow views into memory. Nothing needs a global view yet you get global effects.
Re: The unreasonable effectiveness of modern sort algorithms
#9Good read. Reminds me of the 1 billion row aggregation challenge, especially the perfect hashing part, all the top entries all used it.
Re: The unreasonable effectiveness of modern sort algorithms
#10Isn't this just another case of premature optimization? Shouldn't you be adjusting sorting algorithms only when customer complains?
This is pushing the limits to identify the boundaries