我哪里出错了，实施肯德尔的tau。

Question

所以我找到了这篇关于如何非常有效地计算Kendall's tau的文章O(n log n)，但我似乎无法正确计算。

在本文中，对代码流程进行了概念解释，并在底部给出了代码示例。我正在尝试实现SDTau变体。我得到的值如-1.5与一组测试数字，这是根本不可能的肯德尔的tau。它应该在-1到1之间。

链接:无需登录，打开全文或下载pdf

我的代码

class Kendall_Correlation
{
public static double RUN(List<XYPoint> XY)
{
List<XYPoint> SortedByXThenY = new List<XYPoint>();
SortedByXThenY = XY.OrderBy(XYPoint => XYPoint.X).ThenBy(XYPoint => XYPoint.Y).ToList();
SortedSet<double> tree = new SortedSet<double>();
int NumBefore = 0;
int Equals = 0;
int Discordant = 0;
int concordant = 0;
int ExtraX = 0;
int EXtraY = 0;
int ACount = 0;
int BCount = 0;
int CCount = 0;
int DCount = 0;
int ECount = 0;
double PreviousX = SortedByXThenY[0].X;
double PreviousY = SortedByXThenY[0].Y;
tree.Add(SortedByXThenY[0].Y);
for (int i = 1; i < SortedByXThenY.Count; i++)
{
if (SortedByXThenY[i].X == PreviousX)
{
DCount = 0;
ECount = 1;
}
else
{
if (SortedByXThenY[i].Y == PreviousY)
{
ECount++;
}
else
{
DCount += ECount;
ECount = 1;
}
}
tree.Add(SortedByXThenY[i].Y);
Equals = tree.Where(node => node == SortedByXThenY[i].Y).Count();
NumBefore = tree.Where(node => node < SortedByXThenY[i].Y).Count();
ACount = NumBefore - DCount;
BCount = Equals - ECount;
CCount = i - (ACount + BCount + DCount + ECount - 1);
EXtraY += DCount;
ExtraX += BCount;
concordant += ACount;
Discordant += CCount;
PreviousX = SortedByXThenY[i].X;
PreviousY = SortedByXThenY[i].Y;
}
int n0 = concordant + Discordant + ExtraX;
int n1 = concordant + Discordant + EXtraY;
double tau = ((Double) concordant - (Double) Discordant) / Math.Sqrt(n0 * n1);
return tau;
}
public class XYPoint
{
public double X;
public double Y;
}

是因为我使用的是SortedSet类型吗?从我的理解，SortedSet基本上是相同的AVL树?我的代码也比文章中描述的时间要慢得多。当尝试使用1,000,000个样本时，我的时间是以分钟为单位的

Answer 1

Where方法遍历整个SortedSet以查找满足给定条件的元素。这有一个O(n)的代价，所以你的函数的总体渐近运行时间为O(n²)，而不是你假设的O(n log n)。

为了有效地实现对SortedSet的操作(查找值大于或等于给定值的节点的数量)，可以使用顺序统计树。