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

Enzo Michelangeli enzomich@gmail....
Wed Sep 30 23:07:18 CDT 2009


From: "Sturla Molden" <sturla@molden.no>
Sent: Thursday, October 01, 2009 6:03 AM

> 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).

Yes, but that requires a native module.

Enzo 



More information about the Scipy-dev mailing list