4 ms·

> Pearson and other correlation coefficients are linear, O(n), sorting would incur logiarithmic multiplier O(NlogN). > Thus, it is not computationally efficien

by kortex 5y ago

> Pearson and other correlation coefficients are linear, O(n), sorting would incur logiarithmic multiplier O(NlogN). > Thus, it is not computationally efficient. That is not really what I meant. First, I personally consider NlogN the bar for "efficient" as far as algorithms go. Anything polynomial is inefficient, and anything better than NlogN is like, "super efficient" in my mind. Maybe that is a weird opinion, should I update my mental model? My reasoning is a lot of well known algorithms operate in better than polynomial but worse than linear time. Second, sorting is a solved problem. Regardless of theoretical efficiency, we have so many ways to sort things, there is almost always really fast in practice ways of sorting data. I didn't know about sorting networks, that is fascinating!

eru 5y ago
> First, I personally consider NlogN the bar for "efficient" as far as algorithms go. Anything polynomial is inefficient, and anything better than NlogN is like, "super efficient" in my mind. What is efficient and what ain't depends totally on context. For example, for some domains even proving that a problem is in NP (instead of something worse), means that they consider the problem tractable, because we have good solvers for many NP hard problems in practice. For other domains, you want O(1) or O(log n) or O(log* n) etc. In general, P vs NP is such a big deal, because polynomial runtime is generally seen as tractable, and anything worse as intractable. (Btw, O(n log n) _is_ a polynomial runtime, and so is O(N) or even O(1). Though I can see that as a shorthand of notation you are excluding them.)
- kortex 5y ago
  > (Btw, O(n log n) _is_ a polynomial runtime, and so is O(N) or even O(1). Though I can see that as a shorthand of notation you are excluding them.) I mean yes, technically n^1 is a polynomial, but normally this is just called linear. You hit the nail on the head with the last sentence. Here I'm using polynomial to basically mean "n^k, k>1". From a NP vs P point of view, P is considered tractable. But from a "actually writing libraries" point of view, I think software developers consider O(n^2) "kinda bleh" if it can be at all avoided. Also developers tend to give much more weight to the actual coefficients / parallelism potential / practical runtime. Neural networks have superlinear bounds everywhere, but GPU goes brrr. Brass tacks, sorting some tuples and diffing the rank then reducing strikes me as likely to be: - pretty fast even in the naive implementation - sorting is a well trodden field - easy to write things like shaders for - amenable to speculative execution - amenable to divide and conquer So that is what I mean by efficient.
- frutiger 5y ago
  The “P” in NP means a solution to a decision problem is verifiable in polynomial time. The “N” in NP means the solution can be produced by a non-deterministic Turing machine (i.e. a computer that can search the problem space in many dimensions in each step). NP does not mean “non-polynomial” time to produce a solution, otherwise P != NP by definition. Instead P is a subset of NP. The open question is if all decision problems with solutions verifiable in polynomial time can also be produced in polynomial time.
  - deleted 5y ago
    [deleted]
  - eru 5y ago
    Yes. I know that the N stands for non-deterministic. Read my comment carefully, it agrees with everything you write here. (Or at least, does not disagree. It's silent on most of the intricacies.) For many people moving a problem from NP to P means the same as having a tractable solution. See eg Scott Aaronson's writing on the topic.
    - frutiger 5y ago
      > Read my comment carefully Please take a spoon of your own medicine and read my comment even more carefully. I never suggested my comments were a contradiction to yours. I added some information for bystanders that may have read your comment and come to (or reinforced) a wrong conclusion.
      - eru 5y ago
        Thanks for the clarification! Yes, interpreting NP as non-polynomial is a common misunderstanding. Especially because it's 'sort-of almost right'.
      - saurik 5y ago
        (That you were trying to add and not correct was extremely unclear, FWIW.)
anovikov 5y ago
I can only second this. Few algorithms are as efficient as NlogN.
- thesz 5y ago
  Compare Fourier (O(NlogN)) and wavelet (O(N)) transforms. Both can be used for similarity (correlation) search through projections.
ummonk 5y ago
Indeed, in practice the logN factor can only get so big, even if N is taken to be the number of particles in the observable universe.
- deleted 5y ago
  [deleted]
HelloNurse 5y ago
> Second, sorting is a solved problem. Regardless of theoretical efficiency, we have so many ways to sort things, there is almost always really fast in practice ways of sorting data. By the same reasoning, economy would be a solved problem: you just need to have money. Computing correlation by sorting a large amount of samples instead of reading them once is a cost difference that can make your data processing practically infeasible despite the efficiency of sorting algorithms.

by kortex 5y ago

eru 5y ago

> First, I personally consider NlogN the bar for "efficient" as far as algorithms go. Anything polynomial is inefficient, and anything better than NlogN is like, "super efficient" in my mind. What is efficient and what ain't depends totally on context. For example, for some domains even proving that a problem is in NP (instead of something worse), means that they consider the problem tractable, because we have good solvers for many NP hard problems in practice. For other domains, you want O(1) or O(log n) or O(log* n) etc. In general, P vs NP is such a big deal, because polynomial runtime is generally seen as tractable, and anything worse as intractable. (Btw, O(n log n) _is_ a polynomial runtime, and so is O(N) or even O(1). Though I can see that as a shorthand of notation you are excluding them.)

kortex 5y ago
> (Btw, O(n log n) _is_ a polynomial runtime, and so is O(N) or even O(1). Though I can see that as a shorthand of notation you are excluding them.) I mean yes, technically n^1 is a polynomial, but normally this is just called linear. You hit the nail on the head with the last sentence. Here I'm using polynomial to basically mean "n^k, k>1". From a NP vs P point of view, P is considered tractable. But from a "actually writing libraries" point of view, I think software developers consider O(n^2) "kinda bleh" if it can be at all avoided. Also developers tend to give much more weight to the actual coefficients / parallelism potential / practical runtime. Neural networks have superlinear bounds everywhere, but GPU goes brrr. Brass tacks, sorting some tuples and diffing the rank then reducing strikes me as likely to be: - pretty fast even in the naive implementation - sorting is a well trodden field - easy to write things like shaders for - amenable to speculative execution - amenable to divide and conquer So that is what I mean by efficient.
frutiger 5y ago
The “P” in NP means a solution to a decision problem is verifiable in polynomial time. The “N” in NP means the solution can be produced by a non-deterministic Turing machine (i.e. a computer that can search the problem space in many dimensions in each step). NP does not mean “non-polynomial” time to produce a solution, otherwise P != NP by definition. Instead P is a subset of NP. The open question is if all decision problems with solutions verifiable in polynomial time can also be produced in polynomial time.
- deleted 5y ago
  [deleted]
- eru 5y ago
  Yes. I know that the N stands for non-deterministic. Read my comment carefully, it agrees with everything you write here. (Or at least, does not disagree. It's silent on most of the intricacies.) For many people moving a problem from NP to P means the same as having a tractable solution. See eg Scott Aaronson's writing on the topic.
  - frutiger 5y ago
    > Read my comment carefully Please take a spoon of your own medicine and read my comment even more carefully. I never suggested my comments were a contradiction to yours. I added some information for bystanders that may have read your comment and come to (or reinforced) a wrong conclusion.
    - eru 5y ago
      Thanks for the clarification! Yes, interpreting NP as non-polynomial is a common misunderstanding. Especially because it's 'sort-of almost right'.
    - saurik 5y ago
      (That you were trying to add and not correct was extremely unclear, FWIW.)

anovikov 5y ago

I can only second this. Few algorithms are as efficient as NlogN.

thesz 5y ago
Compare Fourier (O(NlogN)) and wavelet (O(N)) transforms. Both can be used for similarity (correlation) search through projections.

ummonk 5y ago

Indeed, in practice the logN factor can only get so big, even if N is taken to be the number of particles in the observable universe.

deleted 5y ago
[deleted]

HelloNurse 5y ago

> Second, sorting is a solved problem. Regardless of theoretical efficiency, we have so many ways to sort things, there is almost always really fast in practice ways of sorting data. By the same reasoning, economy would be a solved problem: you just need to have money. Computing correlation by sorting a large amount of samples instead of reading them once is a cost difference that can make your data processing practically infeasible despite the efficiency of sorting algorithms.