10 ms·

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 o

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
"typing goo". Generally complaining about the methods used by someone with a novel-peer reviewed result and demanding further and further reductive summarization on your terms, defining said terms with phrases like "typing goo" is bad form. Further suggesting a lack of credibility by suggesting press coverage should be in place is confrontational. I lost my temper after you did these things a few times. I apologize. And yes, it can get O(n) performance with Arbitrary length integers. These analysis exclude underlying comparison times.
- AlexCoventry 8y ago
  Thanks for the feedback. > suggesting a lack of credibility by suggesting press coverage should be in place is confrontational. You edited out the context I was responding to, there. As I recall, you were originally explaining the "six years" in terms of it just being hard to get academic results into the mainstream. That seemed extremely unlikely for such a well-known result. I'm not bothered by your invective or personal attacks, but editing your comments so that my responses are out of context is pretty disturbing.
  - KirinDave 8y ago
    I edited a cloned paragraph with a missing sentence that was accidentally added. I prepared that reply on mobile, and that can happen because you don't see scroll bars. The literal and figurative content weren't changed. I just removed duplication and improve the flow of the post.
- AlexCoventry 8y ago
  Oh, BTW, I love types. I'm programming in OCaml at the moment. I just couldn't see the relevance.
  - KirinDave 8y ago
    Did you try?

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

"typing goo". Generally complaining about the methods used by someone with a novel-peer reviewed result and demanding further and further reductive summarization on your terms, defining said terms with phrases like "typing goo" is bad form. Further suggesting a lack of credibility by suggesting press coverage should be in place is confrontational. I lost my temper after you did these things a few times. I apologize. And yes, it can get O(n) performance with Arbitrary length integers. These analysis exclude underlying comparison times.

AlexCoventry 8y ago
Thanks for the feedback. > suggesting a lack of credibility by suggesting press coverage should be in place is confrontational. You edited out the context I was responding to, there. As I recall, you were originally explaining the "six years" in terms of it just being hard to get academic results into the mainstream. That seemed extremely unlikely for such a well-known result. I'm not bothered by your invective or personal attacks, but editing your comments so that my responses are out of context is pretty disturbing.
- KirinDave 8y ago
  I edited a cloned paragraph with a missing sentence that was accidentally added. I prepared that reply on mobile, and that can happen because you don't see scroll bars. The literal and figurative content weren't changed. I just removed duplication and improve the flow of the post.
AlexCoventry 8y ago
Oh, BTW, I love types. I'm programming in OCaml at the moment. I just couldn't see the relevance.
- KirinDave 8y ago
  Did you try?