5 ms·

Where is the Haskell implementation? Are there public benchmarks of its asymptotic performance? I'm pretty sure a worst-case linear sorting algorithm would hav

Where is the Haskell implementation? Are there public benchmarks of its asymptotic performance? I'm pretty sure a worst-case linear sorting algorithm would have multiple NYT articles about it. EDIT: The edits to the parent since I made this comment make it look a bit silly. It made more sense in the context I was initially responding to. EDIT 2: Thanks for linking the paper. From there: > As Proposition 1.1 and the corresponding well-known combinatorial lower bound of Ω(n log n) (Knuth 1998, Section 5.3.1) for comparison-based sorting show, we cannot accomplish efficient generic partitioning and linear-time sorting by using black-box binary comparison functions as specifications of equivalence or ordering relations. Instead, we show how to construct efficient discriminators by structural recursion on specifications defined compositionally in an expressive domain-specific language for denoting equivalence and ordering relations. Which sounds like the advantage I speculated on in the grandchild below. I understand, now, and it's a nice result. Thanks for pointing it out.

KirinDave 8y ago
https://hackage.haskell.org/package/discrimination https://hackage.haskell.org/package/discrimination Which, by the way, contains boatloads of novel work. It uses internal parallel execution to work around some of the problems with discrimination passes between two groups. Cutting edge stuff. It's haskell. People like you have chips on their shoulder about "typing goo." I'm sure one day someone will write a golang implementation then go to some inventor-centric conference and be hailed as a genius tho, as per usual. But, did you not know about Radix sort or American Flag sort? Counting sort is a common stupid silicon valley interview question, and has been in the ruby code katas since like 2003. So as keen as I am to see this work widely distributed, it's not totally unprecedented the way you make it out to be. Hey, want to know another surprising one? With a proper pre-encoding you can compress an (extremely long) binary value and answer questions about how many bits in a given range have occured (a popcount) in constant time. You can also, by extension, figure out the offset of the Nth hot bit appears, in O(1) time. Pretty surprising, huh? Especially when you realize that the entire space of 32 bit integers is only 512mb as a fully realized bitfield, 32x smaller than actually storing one instance of every integer. See here: http://alexbowe.com/rrr/ http://alexbowe.com/rrr/
- AlexCoventry 8y ago
  > But, did you not know about Radix sort or American Flag sort? Oh, is it that the types somehow mandate roughly evenly-sized ordered partitions at any sample size? If so, I get it, now. Thanks.
  - KirinDave 8y ago
    No I'm afraid they don't. I confess I regret this conversation. I've gotten very little out of it other than a confrontstonal attitude from you and a bunch of confusingly worded challenges.
    - AlexCoventry 8y ago
      If you have any suggestions on how I could have been clearer, I'd welcome them. I'm always glad to learn of flaws in my writing. Can you get linear time even on Haskell's arbitrary-precision `Integer`s?
      - jstimpfle 8y ago
        In general asymptotic analyses (including the well-known O(n log n) bound for comparison based sort) assume a model where operations like compare, swap, arithmetics, etc. are constant-time. So they only work for bounded integers, practically speaking. If you want to know for the general case, you need to adapt your machine model and redo the analysis. Operations will likely be not constant-time but something like log(x) where x is the size of the integer at hand. But of course, that's up to you and what you want to do and how you build your machine.
        KirinDave 8y ago
        I think this isolation is done to critique the algorithm in question in isolation of any underlying structure. What's cool about Discrimination sort is that it does, in fact, can give these linearity guarantees for most kinds of data a computer can represent, including things like strings which have variable length or structs. There are some caveats there, but they're easy enough to work with that nearly every default structure in haskell as seen here: http://hackage.haskell.org/package/discrimination-0.3/docs/Data-Discrimination-Sorting.html#g:1 http://hackage.haskell.org/package/discrimination-0.3/docs/D... Note particularly the instance for [a], and that you can extend it to something like Data.Text's codepoints (and this would work out of the box with something like ByteString's chunked form).

KirinDave 8y ago

https://hackage.haskell.org/package/discrimination https://hackage.haskell.org/package/discrimination Which, by the way, contains boatloads of novel work. It uses internal parallel execution to work around some of the problems with discrimination passes between two groups. Cutting edge stuff. It's haskell. People like you have chips on their shoulder about "typing goo." I'm sure one day someone will write a golang implementation then go to some inventor-centric conference and be hailed as a genius tho, as per usual. But, did you not know about Radix sort or American Flag sort? Counting sort is a common stupid silicon valley interview question, and has been in the ruby code katas since like 2003. So as keen as I am to see this work widely distributed, it's not totally unprecedented the way you make it out to be. Hey, want to know another surprising one? With a proper pre-encoding you can compress an (extremely long) binary value and answer questions about how many bits in a given range have occured (a popcount) in constant time. You can also, by extension, figure out the offset of the Nth hot bit appears, in O(1) time. Pretty surprising, huh? Especially when you realize that the entire space of 32 bit integers is only 512mb as a fully realized bitfield, 32x smaller than actually storing one instance of every integer. See here: http://alexbowe.com/rrr/ http://alexbowe.com/rrr/

AlexCoventry 8y ago
> But, did you not know about Radix sort or American Flag sort? Oh, is it that the types somehow mandate roughly evenly-sized ordered partitions at any sample size? If so, I get it, now. Thanks.
- KirinDave 8y ago
  No I'm afraid they don't. I confess I regret this conversation. I've gotten very little out of it other than a confrontstonal attitude from you and a bunch of confusingly worded challenges.
  - AlexCoventry 8y ago
    If you have any suggestions on how I could have been clearer, I'd welcome them. I'm always glad to learn of flaws in my writing. Can you get linear time even on Haskell's arbitrary-precision `Integer`s?
    - jstimpfle 8y ago
      In general asymptotic analyses (including the well-known O(n log n) bound for comparison based sort) assume a model where operations like compare, swap, arithmetics, etc. are constant-time. So they only work for bounded integers, practically speaking. If you want to know for the general case, you need to adapt your machine model and redo the analysis. Operations will likely be not constant-time but something like log(x) where x is the size of the integer at hand. But of course, that's up to you and what you want to do and how you build your machine.
      - KirinDave 8y ago
        I think this isolation is done to critique the algorithm in question in isolation of any underlying structure. What's cool about Discrimination sort is that it does, in fact, can give these linearity guarantees for most kinds of data a computer can represent, including things like strings which have variable length or structs. There are some caveats there, but they're easy enough to work with that nearly every default structure in haskell as seen here: http://hackage.haskell.org/package/discrimination-0.3/docs/Data-Discrimination-Sorting.html#g:1 http://hackage.haskell.org/package/discrimination-0.3/docs/D... Note particularly the instance for [a], and that you can extend it to something like Data.Text's codepoints (and this would work out of the box with something like ByteString's chunked form).