46 ms·
> but in practice every job where I've been tasked with making something fast, only linear time complexity was good enough. But of course we remember from our
by tshaddox 6y ago
> but in practice every job where I've been tasked with making something fast, only linear time complexity was good enough.
But of course we remember from our CS school that some things simply cannot be done in linear time. I’m not sure what happens when your employer tells you to sort a big list and insists that only linear time complexity is good enough.
- jez 6y agoTo that I find that the answer is usually: find ways to avoid needing to sort the list! This is more viable for many problems than you might otherwise think.
- moomin 6y agoThere’s also vastly faster ways of sorting lists of bounded numbers (or tuples), the most linear being: cut straws of the exact right length labelled with an Id, bang them on a table so the ends without the ids all line up, read the ids back in order. I only said it took linear time, I didn’t say it was fast...
- deleted 6y ago[deleted]
- dbbk 6y ago> some things simply cannot be done in linear time Boy am I glad I didn't take CS
- pjscott 6y agoFor example, a comparison-based sort can't do better than O(n log n) time in general. More information here: https://en.wikipedia.org/wiki/Comparison_sort https://en.wikipedia.org/wiki/Comparison_sort
- renewiltord 6y agoThat's smart. I didn't take Physics and now I can travel faster than EM waves in a vacuum.
- ric2b 6y ago"I'm cool because I never learned some things"
- higerordermap 6y ago"webshit pride"
- dbbk 6y agoIt was a lighthearted comment because the concept went over my head.
- legerdemain 6y agoAnything you didn't learn in Christian Science courses at university, you can find and learn more at your local Christian Science Reading Room! Most cities and towns in the USA have one, and even many airports for people on the go. If you're flying through SFO, you can visit the one in terminal 2!
- machiaweliczny 6y agoRadix sort exists
- tshaddox 6y agoGood luck using that for a big list of strings!
- lomereiter 6y agoIf we are talking about linear in number of characters, an easy answer is building a trie and traversing it left to right. (Cache-friendly variation: https://en.wikipedia.org/wiki/Burstsort https://en.wikipedia.org/wiki/Burstsort)
- codemac 6y agoSure, but it has the classic problems of the memory/storage required for the sort (minimum double all your keys), and a classic math issue relating to it's speed being O(k*N) and since k = number of bits/digits, N can only be as large as the number of bits/digits allow for. This means quicksort and the like end up faster in practice for any "sort this list" operations. Radix/bucket sorting can be SUPER awesome when what you need is a single level of bucketing at all rather than exact order.
- Silhouette 6y agoSure, but it has the classic problems of the memory/storage required for the sort No problem, just create a file of the necessary size on disk if you don't have enough RAM available. Today's comment was brought to you by a large number and the letters big-O and c... where c, a large number, is the hidden constant of proportionality waiting to bite you every time you mention big-O. :-)
- codemac 6y agoHuh? If we're reading from disk, then we DEFINITELY don't want radix, as then it's almost guaranteed that all time will be dominated by loading pages rather than cpu cache locality being leveraged by linear time algorithms - which is what this entire discussion is about.
- toast0 6y agoAt one job we used to joke "i don't care if it's right, as long as it's fast" Of course, it was only half a joke. For some pages, we really did want data quickly, so we were willing to accept stale data or somewhat inaccurate data, it that helped. For other pages/sections, accuracy was more important so caching wasn't possible or invalidation was critical. But product design is always about tradeoffs between what features are desirable, what features are possible, what features are easy to build, and how features interact. Features that are possible but not easy to build can sometimes be replaced with features that are easy to build and close enough.
- wruza 6y agoMaybe they expect you to ask how many elements are out of their place.
- neutronicus 6y agoThe answer is you get stuck maintaining a cache and playing whack a mole with whatever performance metric execs care about this month
- davidmurdoch 6y agoAh, yes, the good ol' Stalin Sort!