c# - 实施 Kendall 的 tau 我哪里错了
问题描述
所以我找到了这篇关于如何非常有效地计算 Kendall 的 tau O(n log n) 的文章。但我似乎无法正确处理。
在文章中,代码流在概念上进行了解释,代码示例在底部。我正在尝试实现 SDTau 变体。我得到了诸如 -1.5 之类的值以及一系列测试数字,这对于 Kendall 的 tau 来说是不可能的。它应该在 -1 和 1 之间。
我的代码
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
Type 吗?根据我的理解,aSortedSet
基本上与 AVL 树相同?我的代码也比文章中描述的时间慢得多。尝试使用 1,000,000 个样本时,我的时间更多
解决方案
该Where
方法遍历整个SortedSet
以找到满足给定条件的元素。这具有 O(n) 成本,因此您的函数的总体渐近运行时间为 O(n 2 ),而不是您假设的 O(n log n)。
为了有效实现您在 SortedSet 上执行的操作(查找其值大于或等于给定值的节点数),您可以使用order statistic tree。
推荐阅读
- python - 如何在pygame中绘制动态箭头?
- cmake - 如何在 CMake 中将变量写入父母的父范围?
- javascript - 如何设置 useEffect 以在第一次使用 eslint-react-hooks 渲染时从 API 获取数据?
- azure-cosmosdb - CosmosDb 首次连接可能需要很多秒
- java - 将 @Value 与 Gauge 框架一起使用
- amazon-web-services - AWS Cognito + aws-amplify:会话状态始终让用户保持登录状态?
- kubernetes - Istio 上消息的模式匹配
- iframe - 为什么我不能在 iframe 中嵌入这个网站?
- google-bigquery - BQ 删除数据集的最快方法
- ruby-on-rails - 无法急切地加载多态关联:item