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

41–47 of 47 posts

Re: Faster than radix sort: Kirkpatrick-Reisch sorting

#41

Post by andrepd »

rumanator wrote: post #7
zem wrote: post #4

Earlier quoted context omitted.

faster in the algorithmic rather than the performance sense

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.

Author knows that:

> 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.

Re: Faster than radix sort: Kirkpatrick-Reisch sorting

#42

Post by zem »

rumanator wrote: post #7
zem wrote: post #4

Earlier quoted context omitted.

faster in the algorithmic rather than the performance sense

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.

it's just a useful and commonly-understood shorthand for "has better asymptotic complexity"

Re: Faster than radix sort: Kirkpatrick-Reisch sorting

#43

Post by vanderZwan »

vanderZwan wrote: post #31

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 s…

So I tried working this out on paper. The simplest variation I could think of:

- 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?

Re: Faster than radix sort: Kirkpatrick-Reisch sorting

#44

Post by Certhas »

gnramires wrote: post #35
Certhas wrote: post #33

Earlier quoted context omitted.

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 la…

The true spherical cow model of circuits.

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...

Re: Faster than radix sort: Kirkpatrick-Reisch sorting

#45

Post by Certhas »

lorenzhs wrote: post #34
Certhas wrote: post #33

Earlier quoted context omitted.

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 ext…

It is not obvious that a two level model is a cleaner way to think about todays memory access, which has 4-5 levels of caches before you even hit possibly NUMA RAM, then an SSD, then a HDD and then maybe big datasets that can only be accessed over the network.

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.

Re: Faster than radix sort: Kirkpatrick-Reisch sorting

#46

Post by elwes5 »

MaxBarraclough wrote: post #40
elwes5 wrote: post #38

Earlier quoted context omitted.

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.

Oh absolutely. The bubble sort sort thing usually comes down to the architecture of the machine. One of the things the O notation kind of hand waves away. On paper some things are faster. But put in 3 levels of cache, a CPU scheduler, a particular ASM instruction flow that makes things faster/slower and suddenly things are different. That is my biggest gripe with the notation. It is good to get you 'close'. But sometimes you just need to fiddle with it and try it. The 'C' bit can get you. On paper bubble sort is always worse. But it can run faster for small sets because the code and is small enough to fit into L1. Whereas maybe a mergesort implementation either the code or the data fits but not both.

Re: Faster than radix sort: Kirkpatrick-Reisch sorting

#47

Post by lorenzhs »

Certhas wrote: post #45
lorenzhs wrote: post #34

Earlier quoted context omitted.

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 ext…

It is not obvious that a two level model is a cleaner way to think about todays memory access, which has 4-5 levels of caches before you even hit possibly NUMA RAM, then an SSD, then a HDD and then maybe big datasets that can only be accessed over the network. 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.

Well you can apply it to any pair of (adjacent) levels of the memory hierarchy. But the main problem with the square root model is that it only models random access time, but not when they are incurred and when data is already in cache. (There are also 2-3 levels of caches, no architecture that I’m aware of has more than 3, maybe 4 if you count the CPU registers but their allocation is usually fixed at compile time)
Post reply on HN