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

21–30 of 47 posts

Re: Faster than radix sort: Kirkpatrick-Reisch sorting

#21

Post by the8472 »

adrianN wrote: post #10
beagle3 wrote: post #8

Earlier quoted context omitted.

In the big-Oh algorithmic complexity sense; in a loose sense, for any pair of implementations (radix sort, kr sort) there exists a word size w and a list size n such that If either w or n increases, the time for radix sort would increase more quickly than for Kr sort - and this, eventually kr would be faster and keep getting faster. (Assuming that the hash can indeed yield average O(1) access, which is probabilistica…

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

The paper mentions huge tables but considers their use uncommon, that has changed since then, at least on linux.

Re: Faster than radix sort: Kirkpatrick-Reisch sorting

#22

Post by lorenzhs »

adrianN wrote: post #10
beagle3 wrote: post #8

Earlier quoted context omitted.

In the big-Oh algorithmic complexity sense; in a loose sense, for any pair of implementations (radix sort, kr sort) there exists a word size w and a list size n such that If either w or n increases, the time for radix sort would increase more quickly than for Kr sort - and this, eventually kr would be faster and keep getting faster. (Assuming that the hash can indeed yield average O(1) access, which is probabilistica…

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 external memory model accounts for a two-level hierarchy, and can be used to reason about cache usage or external memory ("out-of-core")), but other things such as branch (mis-)predictions or virtual memory translation (TLB) are rarely accounted for. That's what the field of Algorithm Engineering is about: designing algorithms that have good worst case guarantees ("Big-O") but that are also really fast when implemented on real-world hardware. (Given the publication list on your website, you probably know all this, but I wanted to expand on it for others)

Re: Faster than radix sort: Kirkpatrick-Reisch sorting

#23

Post by lorenzhs »

jnxx wrote: post #20
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...

Yeah. I am wondering since a while whether well-known algorithms like the binary heap are still efficient on modern architectures, because their random memory access patterns.

For priority queues, which implementation is optimal depends a lot on your workload (do you need addressability, i.e., a decreaseKey operation? What is the typical ratio of insertions to deletions? Are your keys integers?). I found some slide decks that are mostly in English with some German in between that might go some way to answering your question:

[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").

Re: Faster than radix sort: Kirkpatrick-Reisch sorting

#24

Post by contravariant »

jnxx wrote: post #20
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...

Yeah. I am wondering since a while whether well-known algorithms like the binary heap are still efficient on modern architectures, because their random memory access patterns.

Look up cache-oblivious algorithms. Turns out that random memory access can often be improved upon with smart data structures.

Re: Faster than radix sort: Kirkpatrick-Reisch sorting

#26

Post by MaxBarraclough »

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.

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

https://en.wikipedia.org/wiki/Galactic_algorithm

Re: Faster than radix sort: Kirkpatrick-Reisch sorting

#27

Post by cycomanic »

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…

TIL that the fastest way to multiply two numbers is by using a 1729-dimensional Fourier transform. Thanks!

Re: Faster than radix sort: Kirkpatrick-Reisch sorting

#29

Post by MaxBarraclough »

cycomanic wrote: post #27
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…

TIL that the fastest way to multiply two numbers is by using a 1729-dimensional Fourier transform. Thanks!

For a less impractical but still mind-bending algorithm, see Strassen's algorithm for large matrix multiplication.

https://www.geeksforgeeks.org/strassens-matrix-multiplicatio... , see also https://youtube.com/watch?v=ORrM-aSNZUs

Re: Faster than radix sort: Kirkpatrick-Reisch sorting

#30

Post by kurlberg »

adrianN wrote: post #10
beagle3 wrote: post #8

Earlier quoted context omitted.

In the big-Oh algorithmic complexity sense; in a loose sense, for any pair of implementations (radix sort, kr sort) there exists a word size w and a list size n such that If either w or n increases, the time for radix sort would increase more quickly than for Kr sort - and this, eventually kr would be faster and keep getting faster. (Assuming that the hash can indeed yield average O(1) access, which is probabilistica…

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

An amusing, surprising and in hindsight obvious lower bound for average random access speed in an array containing N "words" is N^(1/3) (cube root of N.) I.e., for any realizable computer without new physics.
Post reply on HN