Блог

Поэтому я нашел эту статью о том, как очень эффективно вычислить тау Кендалла O(n log n). Но я, кажется, не могу сделать это правильно.

В статье поток кода объясняется концептуально и приведен пример кода внизу. Я пытаюсь реализовать вариант SDTau. Я получаю такие значения, как -1,5, с массивом тестовых чисел, что просто невозможно для тау Кендалла. Оно должно быть между -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 Тип? Насколько я понимаю, a SortedSet в основном идентичен дереву AVL? Мой код также значительно медленнее, чем показано в статье. Мой больше по величине минут при попытке с выборкой в 1 000 000

Where Метод повторяется по всему SortedSet , чтобы найти элементы, удовлетворяющие заданному условию. Это имеет стоимость O(n), поэтому ваша функция имеет общее асимптотическое время выполнения O(n ²), а не O(n log n), как вы предполагали.

Для эффективной реализации операции, которую вы выполняете с набором сортировки (нахождение количества узлов, значения которых больше или равны заданному значению), вы можете использовать дерево статистики порядка.