I've been trying to get it frontpaged because, despite it's length, it's perhaps one of the most startling papers of this decade. Sadly, it seems like the HN voting gestalt hasn't decided to upvote a paper that's the CS equivalent of breaking the speed of light:
"Generic Top-down Discrimination for Sorting and Partitioning in Linear Time" ->
http://www.diku.dk/hjemmesider/ansatte/henglein/papers/hengl...
(if you're daunted by an 80 page paper as I am, there is also a talk on it: https://www.youtube.com/watch?v=sz9ZlZIRDAg)
It is possible, with some proper insight and approaches, to sort general datastructures in linear time on modern computing hardware. The speed limit of sort is O(n) with some extra constant cost (often accrued by allocation). It works by decomposing and generalizing something akin to radix sort, leveraging a composable pass of linear discriminators to do the work.
There's a followup paper using this to make a very efficient in-memory database that one could easily generalize under something like kademelia and with care I suspect could make something like a better spark core.
http://www.diku.dk/hjemmesider/ansatte/henglein/papers/hengl...
I keep submitting and talking about this but no one seems to pick up on it. This paper is crazy important and every runtime environment SHOULD be scrambling to get this entire approach well-integrated into their stdlib.
Unsurprisingly, Kmett has already implemented it in Haskell (it generalized neatly under the dual of the applicative+alternative functor): https://hackage.haskell.org/package/discrimination
"Generic Top-down Discrimination for Sorting and Partitioning in Linear Time" ->
http://www.diku.dk/hjemmesider/ansatte/henglein/papers/hengl...
(if you're daunted by an 80 page paper as I am, there is also a talk on it: https://www.youtube.com/watch?v=sz9ZlZIRDAg)
It is possible, with some proper insight and approaches, to sort general datastructures in linear time on modern computing hardware. The speed limit of sort is O(n) with some extra constant cost (often accrued by allocation). It works by decomposing and generalizing something akin to radix sort, leveraging a composable pass of linear discriminators to do the work.
There's a followup paper using this to make a very efficient in-memory database that one could easily generalize under something like kademelia and with care I suspect could make something like a better spark core.
http://www.diku.dk/hjemmesider/ansatte/henglein/papers/hengl...
I keep submitting and talking about this but no one seems to pick up on it. This paper is crazy important and every runtime environment SHOULD be scrambling to get this entire approach well-integrated into their stdlib.
Unsurprisingly, Kmett has already implemented it in Haskell (it generalized neatly under the dual of the applicative+alternative functor): https://hackage.haskell.org/package/discrimination