From dsimcha at gmail.com  Wed Feb 24 04:43:57 2010
From: dsimcha at gmail.com (David Simcha)
Date: Tue, 23 Feb 2010 22:43:57 -0500
Subject: [Rd] O(N log N) impl of Kendall's Tau
Message-ID: <4B84A07D.2040003@gmail.com>

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>


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