[Rd] O(N log N) impl of Kendall's Tau

[David Simcha]

I've attached an O(N log N) implementation of Kendall's Tau, which I 
hope will eventually replace the O(N^2) version currently implemented in 
R.  For N = 30,000 it's several hundred times faster than the old 
version.  The core algorithm comes with a lot of tests, which are 
included in the kendall.c file.  However, I've not yet integrated this 
code into the rest of R because, honestly, the code in cor.c is 
inscrutable and intermingles computing Kendall's Tau with dealing with 
missing values and computing other kinds of correlation.  I'd like one 
of the core devs' help with the integration.  The details of the 
algorithm and how to use it are explained in the comments inside kendall.c.

Please let me know what else I can do to help get this improvement 
folded into R.

--David Simcha
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: kendall.c
URL: <https://stat.ethz.ch/pipermail/r-devel/attachments/20100223/077b46e0/attachment.c>