6 ms·

It's complicated enough that you should just watch the whole talk. The paper is 90 pages.

AlexCoventry 8y ago
It's been six years since the talk... Why hasn't someone drilled down through all the irrelevant typing goo, and shown how to sort integers in linear time? Where does the standard proof that optimal algorithms are Ω(n log n) break?
- KirinDave 8y ago
  > Why hasn't someone drilled down through all the irrelevant typing goo, and shown how to sort integers in linear time? I mean, if that's all you want Radix sort and American Flag sort are wikipedia fodder. As for the "typing goo" is, uh, fairly important for how it's derived and what it does. A lot of advanced CS work uses it now, because it's quite powerful. A huge amount of pure-CS research is done in that world. I guess we don't see this work in more contexts because it's just very very difficult to get it right. Edward Kmett, who is globally recognized for his talent in the field, did a haskell implementation which we all use and love, but it's pretty excruciating to implement it outside of a functional and generic language (and it is genuinely hard to do it in a language without general side effects, so you get difficulty from both sides). I think a lot of folks in industry just don't think it matters. Certainly when I talk to my peers they suggest it doesn't matter to their work at all. As for "6 years", they author has continued to push the work. It's also been used in a variety of applications. You can cite search the original paper. https://pdfs.semanticscholar.org/f425/7af9221ca7fe21dc84a049a8545a28a874ae.pdf https://pdfs.semanticscholar.org/f425/7af9221ca7fe21dc84a049... https://scholar.google.dk/scholar?oi=bibs&hl=en&cites=18082135325500003099&as_sdt=5 https://scholar.google.dk/scholar?oi=bibs&hl=en&cites=180821... One particularly interesting work was computing specific types relational algebras producing products in linear time, which is pretty cool: https://dl.acm.org/citation.cfm?id=1706372 https://dl.acm.org/citation.cfm?id=1706372 (btw, sorry, ACM is down tonight they're showing us their cloudflare). This is not new stuff in the world of graduate CS, anymore than succinct data structures or wavelet trees. It's seldom applied in industry, but many of these techniques and sorts are taught as upper division courses in recent, algorithm-and-theory intensive CS programs. That stuff just doesn't make it out of academia very fast these days. Academics face a lot of pushback from industry now with disruptive findings. Look at how Emin Gun Sirer has been blackballed by the cryptocurrency community, for example. Look at how steadfastly folks have stood by JWT despite Lentczner's team's work on a better alternative in Macaroons.
  - AlexCoventry 8y ago
    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/

It's been six years since the talk... Why hasn't someone drilled down through all the irrelevant typing goo, and shown how to sort integers in linear time? Where does the standard proof that optimal algorithms are Ω(n log n) break?

KirinDave 8y ago
> Why hasn't someone drilled down through all the irrelevant typing goo, and shown how to sort integers in linear time? I mean, if that's all you want Radix sort and American Flag sort are wikipedia fodder. As for the "typing goo" is, uh, fairly important for how it's derived and what it does. A lot of advanced CS work uses it now, because it's quite powerful. A huge amount of pure-CS research is done in that world. I guess we don't see this work in more contexts because it's just very very difficult to get it right. Edward Kmett, who is globally recognized for his talent in the field, did a haskell implementation which we all use and love, but it's pretty excruciating to implement it outside of a functional and generic language (and it is genuinely hard to do it in a language without general side effects, so you get difficulty from both sides). I think a lot of folks in industry just don't think it matters. Certainly when I talk to my peers they suggest it doesn't matter to their work at all. As for "6 years", they author has continued to push the work. It's also been used in a variety of applications. You can cite search the original paper. https://pdfs.semanticscholar.org/f425/7af9221ca7fe21dc84a049a8545a28a874ae.pdf https://pdfs.semanticscholar.org/f425/7af9221ca7fe21dc84a049... https://scholar.google.dk/scholar?oi=bibs&hl=en&cites=18082135325500003099&as_sdt=5 https://scholar.google.dk/scholar?oi=bibs&hl=en&cites=180821... One particularly interesting work was computing specific types relational algebras producing products in linear time, which is pretty cool: https://dl.acm.org/citation.cfm?id=1706372 https://dl.acm.org/citation.cfm?id=1706372 (btw, sorry, ACM is down tonight they're showing us their cloudflare). This is not new stuff in the world of graduate CS, anymore than succinct data structures or wavelet trees. It's seldom applied in industry, but many of these techniques and sorts are taught as upper division courses in recent, algorithm-and-theory intensive CS programs. That stuff just doesn't make it out of academia very fast these days. Academics face a lot of pushback from industry now with disruptive findings. Look at how Emin Gun Sirer has been blackballed by the cryptocurrency community, for example. Look at how steadfastly folks have stood by JWT despite Lentczner's team's work on a better alternative in Macaroons.
- AlexCoventry 8y ago
  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/