ENH: Reduce for loops in df.corr(method='kendall')
State: closed

Reduce `for` loops in `df.corr(method='kendall')`

Don't need to loop through lower triangle of the matrix.


Labels:
name: Performance
description: Memory or execution speed performance
name: Numeric Operations
description: Arithmetic, Comparison, and Logical operations

Comments:
this is fine, though actually a better change would be to move this algo to cython (like pearson/spearman) corr already. up for that?

`scipy.stats.kendalltau` is ~ "Inspired by the Java implementation part of the it.unimi.dsi.law package (http://law.dsi.unimi.it/)" 

[Fast (O(n log(n)) implementation](https://github.com/scipy/scipy/commit/fdaee9f553522a7e6a39c639ea1105e3bb679a5b) of Kendall's Tau,  recursively uses mergesorts to count exchanges. More discussion over [here](https://github.com/scipy/scipy/issues/1526)

@jreback -- would this be the implementation to be cythonized?

no need to rewrite the actual tau computation
think the loop can be moved to cython then maybe call out to the scipy routines directly (not 100% sure the c-API is callable though)

This implementation doesn't give much gains. In fact, there isn't much cythonized code here, expect for type declarations.

``` python
import numpy as np
cimport numpy as np

from scipy.stats import kendalltau

#-------------------------------------------------------------------
# Pairwise tau

@cython.boundscheck(False)
@cython.wraparound(False)
def tau(ndarray[float64_t, ndim=2] mat, minp=None):
    cdef:
        Py_ssize_t xi, yi, N, K
        ndarray[float64_t, ndim=2] result
        ndarray[float64_t, ndim=1] ac, bc
        ndarray[uint8_t, ndim=2] mask
        float64_t c

    N, K = (<object> mat).shape

    if minp is None:
        minp = 1

    mat = mat.T
    result = np.empty((K, K), dtype=np.float64)
    mask = np.isfinite(mat).view(np.uint8)
    mask.dtype = bool

    for xi in range(K):
        ac = mat[xi]
        for yi in range(xi + 1):
            bc = mat[yi]
            valid = mask[xi] & mask[yi]
            if valid.sum() < minp:
                c = np.NaN
            elif not valid.all():
                c = kendalltau(ac[valid], bc[valid])[0]
            else:
                c = kendalltau(ac, bc)[0]

            result[xi, yi] = result[yi, xi] = c

    return result
```

Missing something here?

so the time is all taken by calling the `kendalltau` function, right? so that would need to be a cython-level call then to make this benefit (IIRC the implementation of this in scipy is in cython)

As I see here, [scipy.stats.kendalltau](https://github.com/scipy/scipy/blob/master/scipy/stats/stats.py#L3402) implementation is not yet in cython, CMIIW.

ugh. can you profile this and see where the time is spent? 

``` python
In [8]: df = pd.DataFrame(np.random.rand(10000, 10))

In [9]: %prun -l 4 slow.ftau(df)
         650311 function calls (971 primitive calls) in 16.933 seconds

   Ordered by: internal time
   List reduced from 73 to 4 due to restriction <4>

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
649385/55   15.475    0.000   15.475    0.281 stats.py:2858(mergesort)
       55    1.340    0.024   16.928    0.308 stats.py:2792(kendalltau)
       55    0.098    0.002    0.098    0.002 {numpy.core.multiarray.lexsort}
       55    0.007    0.000    0.007    0.000 {range}
```

scipy.stats.kendalltau internally uses custom mergesort function, this seems to be taking up time?

so here's the question. since we are doing many repeated calls, with only slightly different inputs, is their a way to do this operation that sorts much less?

closing, pls reopen if you can fix according to comments