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

Faster than radix sort: Kirkpatrick-Reisch sorting

sortingsearching.com

Post reply on HN
Print view View original

31–40 of 47 posts

Re: Faster than radix sort: Kirkpatrick-Reisch sorting

#31

Post by vanderZwan »

So since this sorting algorithm involves a trie, would there another optimization possibility by using a data structure inspired by the MergedTrie?

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

Re: Faster than radix sort: Kirkpatrick-Reisch sorting

#32

Post by mirekrusin »

nathell wrote: post #15

Written by Tomek Czajka, a 3x TopCoder winner and algorithmic mastermind. Worth following!

Remember him at high school programming olympiads, top place year after year (also on math olympiads and likely other competitions I'd have to recall), everybody admired him.

Re: Faster than radix sort: Kirkpatrick-Reisch sorting

#33

Post by Certhas »

lorenzhs wrote: post #22
adrianN wrote: post #10

Earlier quoted context omitted.

Big-O as commonly used in the CS literature sometimes doesn't translate to Big-O on actual computers. For example virtual memory translation can add a log term where you wouldn't expect it: https://pdfs.semanticscholar.org/1e90/c55362cf7793dc0b2521f6...

That's a common misunderstanding of what "Big-O" is, but rephrased as "the models used for algorithm analysis assume very simple machines that don't represent actual computers all that well" your point is very valid. There's a whole lot of things that our computers do that aren't accounted for in the RAM model (which is most commonly used when analysing sequential algorithms). Memory hierarchies are a big one (the ex…

There is the idea that you should treat memory access as an O(N^.5) operation:

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.

Re: Faster than radix sort: Kirkpatrick-Reisch sorting

#34

Post by lorenzhs »

Certhas wrote: post #33
lorenzhs wrote: post #22

Earlier quoted context omitted.

That's a common misunderstanding of what "Big-O" is, but rephrased as "the models used for algorithm analysis assume very simple machines that don't represent actual computers all that well" your point is very valid. There's a whole lot of things that our computers do that aren't accounted for in the RAM model (which is most commonly used when analysing sequential algorithms). Memory hierarchies are a big one (the ex…

There is the idea that you should treat memory access as an O(N^.5) operation: 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.

Well the problem with that is "this is a curve that roughly fits the data" is a bad way to go about constructing a model. It's a useful and neat observation, but that doesn't make it a good model. It might model random accesses to memory reasonably well (such as traversing a linked list, the example used there), but it doesn't model a scan over an array well. That doesn't make for a useful model. In contrast, the external memory model assumes a fast internal memory of size M (e.g., cache), which can be accessed in constant time, and a slow external memory of infinite size (e.g., RAM) which can only be accessed in blocks of size B (e.g., a cache line). Then you count how many blocks the algorithm needs to read or write. Now, scanning an array of size N takes O(N/B) I/Os, whereas scanning a linked list of the same size takes O(N) I/Os. The complexity of sorting is O(N/B log(N/B)/log(M/B)) I/Os. This models the same behaviour in a much cleaner way, applies equally to all levels of the memory hierarchy (you can also view RAM as the internal memory and a hard disk/SSD as the external memory), and is widely used in what you called "serious academic work" :) See also https://en.wikipedia.org/wiki/External_memory_algorithm

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.

Re: Faster than radix sort: Kirkpatrick-Reisch sorting

#35

Post by gnramires »

Certhas wrote: post #33
lorenzhs wrote: post #22

Earlier quoted context omitted.

That's a common misunderstanding of what "Big-O" is, but rephrased as "the models used for algorithm analysis assume very simple machines that don't represent actual computers all that well" your point is very valid. There's a whole lot of things that our computers do that aren't accounted for in the RAM model (which is most commonly used when analysing sequential algorithms). Memory hierarchies are a big one (the ex…

There is the idea that you should treat memory access as an O(N^.5) operation: 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.

This is somewhat universal. (Some physical insights)

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.

Re: Faster than radix sort: Kirkpatrick-Reisch sorting

#36

Post by lorenzhs »

MaxBarraclough wrote: post #26
rumanator wrote: post #7

Earlier quoted context omitted.

That's not what "faster" means. Computational complexity means expected asymptotic behaviour followig certain assumptions. More often than not don't happen in the real world, or don't take in consideration real-world properties such as tiered cache and the impact of cache misses.

You're being downvoted, but it seems like a fair point. 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 nonethel…

Same as approximately nobody (who did their homework) uses Fibonacci heaps, even though their theoretical running time is fantastic. Turns out that using a binary heap is faster in practice (and binary heaps are far from optimal, see my sibling comment).

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.

Re: Faster than radix sort: Kirkpatrick-Reisch sorting

#37

Post by naasking »

Certhas wrote: post #33
lorenzhs wrote: post #22

Earlier quoted context omitted.

That's a common misunderstanding of what "Big-O" is, but rephrased as "the models used for algorithm analysis assume very simple machines that don't represent actual computers all that well" your point is very valid. There's a whole lot of things that our computers do that aren't accounted for in the RAM model (which is most commonly used when analysing sequential algorithms). Memory hierarchies are a big one (the ex…

There is the idea that you should treat memory access as an O(N^.5) operation: 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.

> I am not sure if any serious academic work has been built on this model, but it's a nice short hand.

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.

Re: Faster than radix sort: Kirkpatrick-Reisch sorting

#38

Post by elwes5 »

MaxBarraclough wrote: post #26
rumanator wrote: post #7

Earlier quoted context omitted.

That's not what "faster" means. Computational complexity means expected asymptotic behaviour followig certain assumptions. More often than not don't happen in the real world, or don't take in consideration real-world properties such as tiered cache and the impact of cache misses.

You're being downvoted, but it seems like a fair point. 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 nonethel…

Big O gets you in the right ballpark of what to look at. That extra 'C' bit that gets left out can doom it to be worse than other items though.

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.

Re: Faster than radix sort: Kirkpatrick-Reisch sorting

#39

Post by MaxBarraclough »

lorenzhs wrote: post #36
MaxBarraclough wrote: post #26

Earlier quoted context omitted.

You're being downvoted, but it seems like a fair point. 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 nonethel…

Same as approximately nobody (who did their homework) uses Fibonacci heaps, even though their theoretical running time is fantastic. Turns out that using a binary heap is faster in practice (and binary heaps are far from optimal, see my sibling comment). 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 diffe…

> nobody (who did their homework) uses Fibonacci heaps, even though their theoretical running time is fantastic

Sounds similar to the 'Brodal queue'.

Re: Faster than radix sort: Kirkpatrick-Reisch sorting

#40

Post by MaxBarraclough »

elwes5 wrote: post #38
MaxBarraclough wrote: post #26

Earlier quoted context omitted.

You're being downvoted, but it seems like a fair point. 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 nonethel…

Big O gets you in the right ballpark of what to look at. That extra 'C' bit that gets left out can doom it to be worse than other items though. 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.…

> Big O gets you in the right ballpark of what to look at

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.

Post reply on HN