4 ms·

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 c

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
  "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?
Demiurge 8y ago
Thanks for selflessly posting! :)
deleted 8y ago
[deleted]
jstimpfle 8y ago
It's easy to see that you two weren't on the same page for quite a bit. I can't see a confrontational attitude. Please avoid belittling the other commenter - they never asked for a long-winded explanation (slightly bragging?) but were obviously only lacking a bit of essential knowledge (O(n log n) is for comparison based sorts). Anyways, thanks for posting the links, although I'm not sure I will get anything out of it :-)
- KirinDave 8y ago
  Sorry, people come at with me with "typing goo" and I tend to assume the worst in this forum.

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
"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?

Demiurge 8y ago

Thanks for selflessly posting! :)

deleted 8y ago

[deleted]

jstimpfle 8y ago

It's easy to see that you two weren't on the same page for quite a bit. I can't see a confrontational attitude. Please avoid belittling the other commenter - they never asked for a long-winded explanation (slightly bragging?) but were obviously only lacking a bit of essential knowledge (O(n log n) is for comparison based sorts). Anyways, thanks for posting the links, although I'm not sure I will get anything out of it :-)

KirinDave 8y ago
Sorry, people come at with me with "typing goo" and I tend to assume the worst in this forum.