Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The unreasonable effectiveness of modern sort algorithms

github.com

Post reply on HN
Print view View original

41–50 of 62 posts

Re: The unreasonable effectiveness of modern sort algorithms

#41

Post by bluGill »

wizardforhire wrote: post #32
lukaslalinsky wrote: post #20

There is one sentence I really took out from the years at university, it was at a database implementation course: > If you have a trouble solving some problem, see if sorting the data first helps. I feel that sorting data is the ultimate computer science hack. Many, many, classes of problems turn into O(log n) problems, once you sort your input in some way. It might not be the most effective way of solving the proble…

Side note: this works great for fermions as well… To save the densest among you the oh so tedious task of extrapolation here are a some anecdotal examples. Dishwasher: Sort your dishes when you pull them out. Cut your walking time to the minimal possible steps, think of this like accessing cache data. Enjoy the now painless benefit of constantly clean dishes and kitchen. Short story: Some friends had a geodesic dome…

Just be careful. Often there are goals other than efficiency. If you get the dishwasher unloaded while cooking - but burn the meal that was a loss. you might be able to do something else while unloading the dishwasher if your sort order is less effient. Or sometimes sorting is less efficent as there isn't enough to do as to make up for the overhead of sorting.

Re: The unreasonable effectiveness of modern sort algorithms

#42

Post by kibwen »

boothby wrote: post #33
lukaslalinsky wrote: post #20

There is one sentence I really took out from the years at university, it was at a database implementation course: > If you have a trouble solving some problem, see if sorting the data first helps. I feel that sorting data is the ultimate computer science hack. Many, many, classes of problems turn into O(log n) problems, once you sort your input in some way. It might not be the most effective way of solving the proble…

It's funny because the opposite is often true as well: if you're having trouble solving a problem quickly, randomize the data and try again.

Sometimes these are even the same approach: https://en.wikipedia.org/wiki/Bogosort

Re: The unreasonable effectiveness of modern sort algorithms

#44

Post by j_not_j »

kwertyoowiyop wrote: post #17
creata wrote: post #11

Earlier quoted context omitted.

"The Unreasonable Effectiveness of Mathematics in the Natural Sciences" is one of those titles that gets imitated a lot for some reason. Maybe even more than "Goto Considered Harmful".

Coming next: “What we talk about when we talk about modern sort algorithms”

Ascending is all you need.

Re: The unreasonable effectiveness of modern sort algorithms

#46

Post by wizardforhire »

bluGill wrote: post #41
wizardforhire wrote: post #32

Earlier quoted context omitted.

Side note: this works great for fermions as well… To save the densest among you the oh so tedious task of extrapolation here are a some anecdotal examples. Dishwasher: Sort your dishes when you pull them out. Cut your walking time to the minimal possible steps, think of this like accessing cache data. Enjoy the now painless benefit of constantly clean dishes and kitchen. Short story: Some friends had a geodesic dome…

Just be careful. Often there are goals other than efficiency. If you get the dishwasher unloaded while cooking - but burn the meal that was a loss. you might be able to do something else while unloading the dishwasher if your sort order is less effient. Or sometimes sorting is less efficent as there isn't enough to do as to make up for the overhead of sorting.

Good point, thats how I feel about to do lists most of the time.

I think the key insight you make is recognizing that attempting to do two things at the same time is asking for disaster. Concurrency in my experience is all about rhythm and timing… something humans in their default state are notoriously bad at ie without training and practice. The best approach in my experience is doing one thing at a time with focus and conviction until completion, then move on to the next thing. If concurrency is desired then understanding duration and prioritizing items via dependencies is of utmost prudence. But paraphrasing Michel de Montaigne… something something about something

Re: The unreasonable effectiveness of modern sort algorithms

#47

Post by loa_in_ »

spiffytech wrote: post #13
bob1029 wrote: post #8

I 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 selecti…

Could you give an example of reframing a problem from totally ordered complete data to a sampled tournament? I can imagine cases amenable to sampling, but since sampled data is smaller I'm not sure why I wouldn't just sort it.

Sorting doesn't yield an ELO score for each item. Though tournament is a form of sorting. It's like instrumented sorting.

Re: The unreasonable effectiveness of modern sort algorithms

#48

Post by gpvos »

dvh wrote: post #12
codegladiator wrote: post #10

Earlier quoted context omitted.

This is pushing the limits to identify the boundaries

Also known as premature optimization. You had to literally invent new dataset just to show there is a difference. You are inventing problems, stop doing that!

This is research, not production code. Premature optimization is irrelevant.

Re: The unreasonable effectiveness of modern sort algorithms

#49

Post by bluGill »

wizardforhire wrote: post #46
bluGill wrote: post #41

Earlier quoted context omitted.

Just be careful. Often there are goals other than efficiency. If you get the dishwasher unloaded while cooking - but burn the meal that was a loss. you might be able to do something else while unloading the dishwasher if your sort order is less effient. Or sometimes sorting is less efficent as there isn't enough to do as to make up for the overhead of sorting.

Good point, thats how I feel about to do lists most of the time. I think the key insight you make is recognizing that attempting to do two things at the same time is asking for disaster. Concurrency in my experience is all about rhythm and timing… something humans in their default state are notoriously bad at ie without training and practice. The best approach in my experience is doing one thing at a time with focus…

Concurrency is very hard for humans to get right. It can work in a factory where we can analysis everything and figure out that someone has time to do two jobs (you might be able to put the windshield wipers on at the end of the line and then turn to a different line to put the seat recline buttons on - if the lines are arranged for this and the bottleneck is somewhere else on the line). However most home jobs are not the repetitive and so you can never get good enough at something to take advantage of it. (maybe if you always make the same meal every night you will know where the breaks are and can do something else - but most people like more variety in life)

Re: The unreasonable effectiveness of modern sort algorithms

#50

Post by wizardforhire »

bluGill wrote: post #49
wizardforhire wrote: post #46

Earlier quoted context omitted.

Good point, thats how I feel about to do lists most of the time. I think the key insight you make is recognizing that attempting to do two things at the same time is asking for disaster. Concurrency in my experience is all about rhythm and timing… something humans in their default state are notoriously bad at ie without training and practice. The best approach in my experience is doing one thing at a time with focus…

Concurrency is very hard for humans to get right. It can work in a factory where we can analysis everything and figure out that someone has time to do two jobs (you might be able to put the windshield wipers on at the end of the line and then turn to a different line to put the seat recline buttons on - if the lines are arranged for this and the bottleneck is somewhere else on the line). However most home jobs are no…

Absolutely!

And even this is a challenge!

We just weren’t built for doing more than one thing at a time out of the gate, and context switching is our achilles heal. (Not to say there aren’t extraordinary examples to the contrary, its just not the default and requires a lot of practice. I’m thinking specifically about musicians but most people aren’t ready for the kind of commitment necessary to reinforce the neural pathways required to develop the skill)

You hit on something really deep about variety. A conversation near and dear to my heart, sadly this forum is not really conducive to the kind of long form dialog the topic is deserving of.

Post reply on HN