[SciPy-dev] Fast (O(n log(n)) ) implementation of Kendall Tau

Sturla Molden sturla@molden...
Wed Sep 30 17:03:49 CDT 2009


Enzo Michelangeli skrev:
> Dear all,
>
> A few days ago I posted to http://projects.scipy.org/scipy/ticket/999 a 
> drop-in replacement for scipy.stats.kendalltau. My code implements the 
> algorithm with complexity O(n log()) described by William R. Knight in a 
> paper of 1966 archived at http://www.jstor.org/pss/2282833 , whereas the 
> function currently in SciPy has complexity O(n^2), which makes it unusable 
>   
There is also:

http://projects.scipy.org/scipy/ticket/893

It has a contigency table version that would be fast for large data 
sets, in theory O(n).


Sturla Molden




More information about the Scipy-dev mailing list