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.
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.
I only said it took linear time, I didn’t say it was 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.
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.
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. :-)
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.
Boy am I glad I didn't take CS