Faster than radix sort: Kirkpatrick-Reisch sorting(sortingsearching.com) |
Faster than radix sort: Kirkpatrick-Reisch sorting(sortingsearching.com) |
My first thought would be to split the list of numbers into a prefix and a suffix part and building two tries connected at the leaves[1][2], replacing the trie used in the article. Then we sort both tries using the Kirkpatrick-Reisch method (but in reverse order for the suffix trie so that the final result is sorted correctly), and finally we would have to reconnect the two while walking the tries.
[0] https://journals.plos.org/plosone/article?id=10.1371/journal...
[1] more or less, the MT in the linked paper works a bit differently but also has a different use-case in mind.
[2] Also I have no idea if it make sense to have two depth 2 tries, or if there is another algorithm out there with two depth 1 tries that _kind_ of looks like this algorithm
- split the numbers into a top and bottom half (from now on: prefix and suffix) (linear time)
- make an unordered suffix trie (linear time). First level has suffixes as, second level has prefixes
- make a (recursively sorted) ordered prefix set, and a (recursively sorted) ordered suffix set
- initiate an ordered prefix trie, but only the first level for now - that is, don't insert suffixes yet (linear time over the ordered prefix set)
- in order of the ordered suffix set, walk over the suffix trie and for each prefix leaf insert the parent suffix into the appropriate prefix bucket in the prefix trie (linear time)
- now we can walk the prefix trie in order and combine prefix and suffix again (like in the article)
This feels like it should have comparable computational complexity - as far as I can see the only real difference is that it recursively sorts twice as often (once for the prefix set and once for the suffix set). Either way it still seems to have horrible memory overhead, requiring a trie for each level of recursion and all that.
Then I realized that if we are at the base case where prefix/suffix can be sorted with a counting sort, then the above can actually be simplified to LSB radix sort where we sort the suffixes into a temporary secondary array, and the prefixes from the secondary array into the original array (I think we can safely say that using a plain array of n elements has both lower memory overhead and better computational performance than a trie with n leaves). But... couldn't I then optimize the entire recursion into an LSB radix sort? Which would imply it must have... worse time complexity than Kirkpatrick-Reisch sorting? Wait what? Where did I go wrong then?
My inclination is that this would be slower than "standard" high perf radix sorting, but I'm not sure if the high level overview of this algorithm represents an equivalent level of implementation.
Wouldn't this decrease again for large enough n, and even go negative after n=2^(w * 2)?
O(n+max(0,log(w/log n)))Benchmarks?
That said, word size w is, in almost all integer dieting problems, bounded by 128 (by 64 or even 32 with high probability) which makes it acceptable to regard as “constant” in which case both sorts are essentially O(n) and it all depends on specific implementations (with radix sort likely significantly faster in practice)
1. It scans in linear order, so if you tune your radix size to L1/L2 cache it will happily beat other "faster" algorithms thanks to the prefetcher.
2. If preserves ordering for keys with the same value.
#2 makes is a really good depth-sorting algorithm for alpha rendering, and #1 just makes it darn fast. There's a nice floating point implementation out there for it as well.
When it applies, there are essentially no faster algorithms - it’s O(n) if the word size is constant (it often is), which cannot be beat asymptotically. kr sort is only asymptotically better if word size is considered variable.
It’s irrelevant if you have no radix to sort on - comparison sort is provably at least O(n log n) which is slower.
That's called a stable sort, and it's a standard property present in many sorting algorithms.
https://github.com/emilk/ram_bench
I am not sure if any serious academic work has been built on this model, but it's a nice short hand.
Naively, to achieve optimal access time, you can pack your memory within a sphere of radius R, and R=O(N^(1/3)).
But, for large R you start having cooling problems. If each memory element needs some power P to operate, then the total power consumption is P×N = O(R^3). But your area is only 4pi R^2, so the power flow per unit area is O(R)=O(N^(1/3)). So if it has large radius, and it has limited thermal conductivity, your memory will melt (since temperature ~ power flow^(1/3) (Plank's law)).
The threshold for stable temperatures at any radius is memory access as O(N^(1/2)).
This analysis is valid for general computing and circuits, but since computers are usually modeled as memory machines I think that's sufficient (?).
Obs: Why, or how, is the human brain roughly spherical then? Because we have a very effective (water based) cooling system. Still, if it got large enough, and you admit limited flow rates of water and such, cooling eventually would be limiting. If you immediately thought of elephants, so did I, and this may be linked to their fantastic large ears:
https://asknature.org/strategy/large-ears-aid-cooling/
I love how everything is connected.
Obs2: Yes this is related to the Bekenstein bound, but much more relevant of course (because existing RAM is almost thermally limited and you need black hole densities to achieve bekenstein bound). The memories we use are organized in (mostly) flat packages.
Furthermore, the introduction in the article you linked misunderstands Big-O notation so incredibly fundamentally that I don't think the author has done their background reading on machine models and Big-O notation.
Not that nmodel specifically, but cache-oblivious data structures are specifically designed to scale well in a hierarchical cache model, no matter the cache block size. So they scale excellently across L1 cache all the way down to hard disk.
[1] https://algo2.iti.kit.edu/sanders/courses/algen20/vorlesung.... slide 180-207, there are some up-to-date measurements on slide 204
[2] https://nms.kcl.ac.uk/stefan.edelkamp/lectures/ae/slide/AE-A...
There are also parallel priority queues which might be useful depending on your problem, especially if it can be reformulated to operate on batches ("give me the 20 smallest items", "insert these 50 items").
My favourite example: multiplication of very large square matrices. The algorithms with the best time complexity are never used in the real world. Under no realistic circumstances would they offer the best performance.
In that case, it's not cache behaviour or branch-prediction that dooms the algorithm, but very intensive steps in the algorithm that are nonetheless constant-time, and so don't impact the complexity theoretic properties.
Do we describe such algorithms as the 'fastest'? I wouldn't. They have the lowest time complexity. Not the same thing.
Models are there to enable us to reason about things that are too complex to reason about directly. They're always going to lose information. Sometimes using a different model is the right answer, and sometimes you need practical experiments to determine what actually works.
Sounds similar to the 'Brodal queue'.
For example for very small sets of numbers you could basically pre-sort every combination there is then have a very large lookup table. Much like a rainbow table for passwords. Your O is basically a binary search lookup O(log(n)) or even better O(1) if you can make it linear. However, the upfront cost is huge and storage cost is huge, lookup would probably be big too. Hmm, now that I think about it this could be an interesting thing to mess with. Also at this time anything past 4 bytes would be unusable. Hmm, maybe later. Like you point out a 'galactic alg'. Portions of that thinking can be pulled out and used for other items though.
With sorting using the comparison is a good proxy for if it might perform well. But it is just that, a proxy. Like the weird sort I just made up. There is probably a few shifts and muls in there. Those are decently expensive and can blow your perf right out of the water.
Generally I'd say that's true, but even that depends on context. For sorting very small arrays, on typical hardware, you can't beat bubble-sort and insertion-sort.
https://www.geeksforgeeks.org/strassens-matrix-multiplicatio... , see also https://youtube.com/watch?v=ORrM-aSNZUs
> To achieve agreement when discussing the speed of a sorting algorithm, it’s necessary to establish some common ground. How do we measure speed? There is a well-established model – the von Neumann computer, or unit-cost RAM model – widely used by computer scientists to evaluate algorithms without introducing all the complexities of real-world computers. This model doesn’t account for some important things, such as the performance gap between RAM and CPU, but typically gives good approximations of real-life performance.
I do wonder though if this is really the mechanism behind the observed N^.5 law. As you allude to with Bekenstein, just because there is an eventual physical limit doesn't mean the structure of real hardware mirrors it.
Also, we are not limited to dissipation to transport heat away...
But then, I am a physicist, not an engineer, so to me starting from empirical observations is actually a very good way to construct a model.