For floats, you can just use the integer representation, when the numbers are positive. This applies to the distance example. For bigints, you first sort by bit/byte-length. And then you sort from the most significant byte. For ratios you simply make all denominators the same -- the least common multiple of the denominators. This might not work all the time, when overflow happens, then you fallback to std::sort
The generalization of the string sorting would work for strings having only ASCII chars, but it would fail for strings having UTF8 which may have 1 - 4 bytes per character. How would you solve that?
"Generic Top-down Discrimination for Sorting and Partitioning in Linear Time" by Fritz Henglein (2010) www.diku.dk/hjemmesider/ansatte/henglein/papers/henglein2011a.pdf The author generalizes Radix/American Flag Sort to arbitrary algebraic data types, including recursive ones.
Thanks for sharing! Is there a shorter version that skips the mathematical rigour parts that I'm sure are in order? 82 pages is a bit much to dig through...
By the way, if you read the blog posts he mentions this too: "A much more promising approach is this paper by Fritz Henglein. I didn’t read all of the paper but it looks like he did something very similar to what I did, except he did it five years ago. According to his graphs, his sorting algorithm is also much faster than older sorting algorithms. So I think he did great work, but for some reason nobody has heard about it. The lesson that I would take from that is that if you’re doing work to improve performance of algorithms, don’t do it in Haskell. The problem is that sorting is slow in Haskell to begin with. So he is comparing his algorithm against slow sorting algorithms and it’s easy to beat slow sorting algorithms. I think that his algorithm would be faster than std::sort if he wrote it in C++, but it’s hard to tell." probablydance.com/2017/01/17/faster-sorting-algorithm-part-2/
This is brilliant. Very informative, step by step. Thanks for the presentation.
Glad it was helpful!
This is brilliant. Good job!
For floats, you can just use the integer representation, when the numbers are positive. This applies to the distance example.
For bigints, you first sort by bit/byte-length. And then you sort from the most significant byte.
For ratios you simply make all denominators the same -- the least common multiple of the denominators. This might not work all the time, when overflow happens, then you fallback to std::sort
The generalization of the string sorting would work for strings having only ASCII chars, but it would fail for strings having UTF8 which may have 1 - 4 bytes per character. How would you solve that?
Sort treating them ASCII. Then unicode sort wrong sorted parts.
Slides are super delayed though...
Could you post a working source code of your example.
github.com/skarupke/ska_sort/
"Generic Top-down Discrimination for Sorting and Partitioning in Linear Time" by Fritz Henglein (2010)
www.diku.dk/hjemmesider/ansatte/henglein/papers/henglein2011a.pdf
The author generalizes Radix/American Flag Sort to arbitrary algebraic data types, including recursive ones.
Thanks for sharing! Is there a shorter version that skips the mathematical rigour parts that I'm sure are in order? 82 pages is a bit much to dig through...
By the way, if you read the blog posts he mentions this too:
"A much more promising approach is this paper by Fritz Henglein. I didn’t read all of the paper but it looks like he did something very similar to what I did, except he did it five years ago. According to his graphs, his sorting algorithm is also much faster than older sorting algorithms. So I think he did great work, but for some reason nobody has heard about it. The lesson that I would take from that is that if you’re doing work to improve performance of algorithms, don’t do it in Haskell. The problem is that sorting is slow in Haskell to begin with. So he is comparing his algorithm against slow sorting algorithms and it’s easy to beat slow sorting algorithms. I think that his algorithm would be faster than std::sort if he wrote it in C++, but it’s hard to tell."
probablydance.com/2017/01/17/faster-sorting-algorithm-part-2/