Почему вставка в мое дерево быстрее при сортированном вводе, чем при произвольном вводе?

Question

Теперь я всегда слышал, что двоичные деревья поиска быстрее строятся из случайно выбранных данных, чем из упорядоченных данных, просто потому, что упорядоченные данные требуют явной перебалансировки, чтобы поддерживать высоту дерева на минимуме.

Недавно я реализовал неизменный трепп, особый вид бинарного дерева поиска, которое использует рандомизацию, чтобы поддерживать себя относительно сбалансированным. В отличие от того, что я ожидал, я обнаружил, что могу последовательно строить трейп примерно в 2 раза быстрее и, как правило, лучше сбалансировать упорядоченные данные, чем неупорядоченные, - и я понятия не имею, почему.

Вот моя реализация трэпа:

• http://pastebin.com/VAfSJRwZ

А вот и тестовая программа:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;

namespace ConsoleApplication1
{

    class Program
    {
        static Random rnd = new Random();
        const int ITERATION_COUNT = 20;

        static void Main(string[] args)
        {
            List<double> rndTimes = new List<double>();
            List<double> orderedTimes = new List<double>();

            rndTimes.Add(TimeIt(50, RandomInsert));
            rndTimes.Add(TimeIt(100, RandomInsert));
            rndTimes.Add(TimeIt(200, RandomInsert));
            rndTimes.Add(TimeIt(400, RandomInsert));
            rndTimes.Add(TimeIt(800, RandomInsert));
            rndTimes.Add(TimeIt(1000, RandomInsert));
            rndTimes.Add(TimeIt(2000, RandomInsert));
            rndTimes.Add(TimeIt(4000, RandomInsert));
            rndTimes.Add(TimeIt(8000, RandomInsert));
            rndTimes.Add(TimeIt(16000, RandomInsert));
            rndTimes.Add(TimeIt(32000, RandomInsert));
            rndTimes.Add(TimeIt(64000, RandomInsert));
            rndTimes.Add(TimeIt(128000, RandomInsert));
            string rndTimesAsString = string.Join("\n", rndTimes.Select(x => x.ToString()).ToArray());

            orderedTimes.Add(TimeIt(50, OrderedInsert));
            orderedTimes.Add(TimeIt(100, OrderedInsert));
            orderedTimes.Add(TimeIt(200, OrderedInsert));
            orderedTimes.Add(TimeIt(400, OrderedInsert));
            orderedTimes.Add(TimeIt(800, OrderedInsert));
            orderedTimes.Add(TimeIt(1000, OrderedInsert));
            orderedTimes.Add(TimeIt(2000, OrderedInsert));
            orderedTimes.Add(TimeIt(4000, OrderedInsert));
            orderedTimes.Add(TimeIt(8000, OrderedInsert));
            orderedTimes.Add(TimeIt(16000, OrderedInsert));
            orderedTimes.Add(TimeIt(32000, OrderedInsert));
            orderedTimes.Add(TimeIt(64000, OrderedInsert));
            orderedTimes.Add(TimeIt(128000, OrderedInsert));
            string orderedTimesAsString = string.Join("\n", orderedTimes.Select(x => x.ToString()).ToArray());

            Console.WriteLine("Done");
        }

        static double TimeIt(int insertCount, Action<int> f)
        {
            Console.WriteLine("TimeIt({0}, {1})", insertCount, f.Method.Name);

            List<double> times = new List<double>();
            for (int i = 0; i < ITERATION_COUNT; i++)
            {
                Stopwatch sw = Stopwatch.StartNew();
                f(insertCount);
                sw.Stop();
                times.Add(sw.Elapsed.TotalMilliseconds);
            }

            return times.Average();
        }

        static void RandomInsert(int insertCount)
        {
            Treap<double> tree = new Treap<double>((x, y) => x.CompareTo(y));
            for (int i = 0; i < insertCount; i++)
            {
                tree = tree.Insert(rnd.NextDouble());
            }
        }

        static void OrderedInsert(int insertCount)
        {
            Treap<double> tree = new Treap<double>((x, y) => x.CompareTo(y));
            for(int i = 0; i < insertCount; i++)
            {
                tree = tree.Insert(i + rnd.NextDouble());
            }
        }
    }
}

И вот диаграмма, сравнивающая случайное и упорядоченное время вставки в миллисекундах:

Insertions         Random          Ordered         RandomTime / OrderedTime
50                 1.031665        0.261585        3.94
100                0.544345        1.377155        0.4
200                1.268320        0.734570        1.73
400                2.765555        1.639150        1.69
800                6.089700        3.558350        1.71
1000               7.855150        4.704190        1.67
2000               17.852000       12.554065       1.42
4000               40.157340       22.474445       1.79
8000               88.375430       48.364265       1.83
16000              197.524000      109.082200      1.81
32000              459.277050      238.154405      1.93
64000              1055.508875     512.020310      2.06
128000             2481.694230     1107.980425     2.24

Я не вижу в коде ничего, что делает упорядоченный ввод асимптотически быстрее, чем неупорядоченный ввод, поэтому я не могу объяснить разницу.

Почему гораздо быстрее построить треп из упорядоченного ввода, чем из случайного?

Answer 1

Самоуравновешивающиеся деревья существуют для решения проблем, связанных с неслучайно распределенными данными. По определению, они обменивают часть производительности в лучшем случае, чтобы значительно улучшить производительность в худшем случае, связанную с несбалансированными BST, особенно с сортированным вводом.

Вы на самом деле задумываетесь над этой проблемой, потому что медленная вставка случайных и упорядоченных данных является характеристикой любого сбалансированного дерева. Попробуйте на AVL, и вы увидите те же результаты.

У Кэмерона была правильная идея, убрав проверку приоритета, чтобы вызвать наихудший случай. Если вы сделаете это и обработаете свое дерево, чтобы увидеть, сколько перебалансировок происходит для каждой вставки, на самом деле становится совершенно очевидно, что происходит. При вставке отсортированных данных дерево всегда поворачивается влево, а правый дочерний элемент корня всегда пуст. Вставка всегда приводит к ровно одному перебалансированию, поскольку узел вставки не имеет дочерних элементов и рекурсия не происходит. С другой стороны, когда вы запускаете его на случайных данных, почти сразу вы начинаете видеть множественные перебалансировки, происходящие на каждой вставке, целых 5 или 6 из них в наименьшем случае (50 вставок), потому что это происходит на поддеревьях как Что ж.

С включенной проверкой приоритетов, не только затраты на перебалансировку, как правило, дешевле из-за того, что в левое поддерево выталкивается больше узлов (откуда они никогда не выходят, потому что там не происходит вставок), но также они менее вероятны. Зачем? Потому что в трепе узлы с высоким приоритетом плавают наверх, и постоянные левые повороты (не сопровождаемые правыми вращениями) также начинают подталкивать все высокоприоритетные узлы в левое поддерево. В результате перебалансировки происходят реже из-за неравномерного распределения вероятности.

Если вы примените код перебалансировки, вы увидите, что это правда; как для отсортированного, так и для случайного ввода вы получаете почти одинаковое количество поворотов влево, но случайный ввод также дает одинаковое количество поворотов вправо, что в два раза больше. Это не должно удивлять - гауссовский ввод должен приводить к гауссовому распределению вращений. Вы также увидите, что всего лишь на 60-70% больше перебалансировок верхнего уровня для отсортированного ввода, что, возможно , удивительно, и опять же, это связано с тем, что отсортированный ввод искажает естественное распределение приоритетов.

Вы также можете убедиться в этом, проверив полное дерево в конце цикла вставки. При случайном вводе приоритеты имеют тенденцию уменьшаться довольно линейно по уровню; При сортированном вводе приоритеты, как правило, остаются очень высокими, пока не дойдете до одного или двух уровней снизу.

Надеюсь, я проделал приличную работу, объясняя это... дайте мне знать, если что-то из этого слишком расплывчато.

Answer 2

Я запустил ваш код, и я думаю, что это связано с количеством вращений. Во время упорядоченного ввода число вращений является оптимальным, и дереву никогда не придется поворачиваться назад.

Во время случайного ввода дерево должно будет выполнять больше вращений, потому что оно может вращаться взад и вперед.

Чтобы действительно выяснить, мне нужно было бы добавить счетчики для числа левого и правого поворотов для каждого прогона. Вы, вероятно, можете сделать это самостоятельно.

ОБНОВИТЬ:

Я установил точки останова на повороте влево и повороте на ночь. Во время упорядоченного ввода значение поворота никогда не используется. Во время случайного ввода оба удара, и мне кажется, что они используются чаще.

ОБНОВЛЕНИЕ 2:

Я добавил некоторые выходные данные к заказанному прогону из 50 элементов (для ясности подставим целые числа), чтобы узнать больше:

TimeIt(50, OrderedInsert)
LastValue = 0, Top.Value = 0, Right.Count = 0, Left.Count = 0
RotateLeft @value=0
LastValue = 1, Top.Value = 1, Right.Count = 0, Left.Count = 1
LastValue = 2, Top.Value = 1, Right.Count = 1, Left.Count = 1
LastValue = 3, Top.Value = 1, Right.Count = 2, Left.Count = 1
RotateLeft @value=3
RotateLeft @value=2
RotateLeft @value=1
LastValue = 4, Top.Value = 4, Right.Count = 0, Left.Count = 4
LastValue = 5, Top.Value = 4, Right.Count = 1, Left.Count = 4
LastValue = 6, Top.Value = 4, Right.Count = 2, Left.Count = 4
RotateLeft @value=6
LastValue = 7, Top.Value = 4, Right.Count = 3, Left.Count = 4
LastValue = 8, Top.Value = 4, Right.Count = 4, Left.Count = 4
RotateLeft @value=8
RotateLeft @value=7
LastValue = 9, Top.Value = 4, Right.Count = 5, Left.Count = 4
LastValue = 10, Top.Value = 4, Right.Count = 6, Left.Count = 4
RotateLeft @value=10
RotateLeft @value=9
RotateLeft @value=5
RotateLeft @value=4
LastValue = 11, Top.Value = 11, Right.Count = 0, Left.Count = 11
LastValue = 12, Top.Value = 11, Right.Count = 1, Left.Count = 11
RotateLeft @value=12
LastValue = 13, Top.Value = 11, Right.Count = 2, Left.Count = 11
RotateLeft @value=13
LastValue = 14, Top.Value = 11, Right.Count = 3, Left.Count = 11
LastValue = 15, Top.Value = 11, Right.Count = 4, Left.Count = 11
RotateLeft @value=15
RotateLeft @value=14
LastValue = 16, Top.Value = 11, Right.Count = 5, Left.Count = 11
LastValue = 17, Top.Value = 11, Right.Count = 6, Left.Count = 11
RotateLeft @value=17
LastValue = 18, Top.Value = 11, Right.Count = 7, Left.Count = 11
LastValue = 19, Top.Value = 11, Right.Count = 8, Left.Count = 11
RotateLeft @value=19
LastValue = 20, Top.Value = 11, Right.Count = 9, Left.Count = 11
LastValue = 21, Top.Value = 11, Right.Count = 10, Left.Count = 11
RotateLeft @value=21
LastValue = 22, Top.Value = 11, Right.Count = 11, Left.Count = 11
RotateLeft @value=22
RotateLeft @value=20
RotateLeft @value=18
LastValue = 23, Top.Value = 11, Right.Count = 12, Left.Count = 11
LastValue = 24, Top.Value = 11, Right.Count = 13, Left.Count = 11
LastValue = 25, Top.Value = 11, Right.Count = 14, Left.Count = 11
RotateLeft @value=25
RotateLeft @value=24
LastValue = 26, Top.Value = 11, Right.Count = 15, Left.Count = 11
LastValue = 27, Top.Value = 11, Right.Count = 16, Left.Count = 11
RotateLeft @value=27
LastValue = 28, Top.Value = 11, Right.Count = 17, Left.Count = 11
RotateLeft @value=28
RotateLeft @value=26
RotateLeft @value=23
RotateLeft @value=16
RotateLeft @value=11
LastValue = 29, Top.Value = 29, Right.Count = 0, Left.Count = 29
LastValue = 30, Top.Value = 29, Right.Count = 1, Left.Count = 29
LastValue = 31, Top.Value = 29, Right.Count = 2, Left.Count = 29
LastValue = 32, Top.Value = 29, Right.Count = 3, Left.Count = 29
RotateLeft @value=32
RotateLeft @value=31
LastValue = 33, Top.Value = 29, Right.Count = 4, Left.Count = 29
RotateLeft @value=33
RotateLeft @value=30
LastValue = 34, Top.Value = 29, Right.Count = 5, Left.Count = 29
RotateLeft @value=34
LastValue = 35, Top.Value = 29, Right.Count = 6, Left.Count = 29
LastValue = 36, Top.Value = 29, Right.Count = 7, Left.Count = 29
LastValue = 37, Top.Value = 29, Right.Count = 8, Left.Count = 29
RotateLeft @value=37
LastValue = 38, Top.Value = 29, Right.Count = 9, Left.Count = 29
LastValue = 39, Top.Value = 29, Right.Count = 10, Left.Count = 29
RotateLeft @value=39
LastValue = 40, Top.Value = 29, Right.Count = 11, Left.Count = 29
RotateLeft @value=40
RotateLeft @value=38
RotateLeft @value=36
LastValue = 41, Top.Value = 29, Right.Count = 12, Left.Count = 29
LastValue = 42, Top.Value = 29, Right.Count = 13, Left.Count = 29
RotateLeft @value=42
LastValue = 43, Top.Value = 29, Right.Count = 14, Left.Count = 29
LastValue = 44, Top.Value = 29, Right.Count = 15, Left.Count = 29
RotateLeft @value=44
LastValue = 45, Top.Value = 29, Right.Count = 16, Left.Count = 29
LastValue = 46, Top.Value = 29, Right.Count = 17, Left.Count = 29
RotateLeft @value=46
RotateLeft @value=45
LastValue = 47, Top.Value = 29, Right.Count = 18, Left.Count = 29
LastValue = 48, Top.Value = 29, Right.Count = 19, Left.Count = 29
LastValue = 49, Top.Value = 29, Right.Count = 20, Left.Count = 29

Заказанные предметы всегда добавляются к правой стороне дерева, естественно. Когда правая сторона становится больше, чем левая, происходит левый поворот. Ротация никогда не происходит. Новый верхний узел выбирается примерно каждый раз, когда дерево удваивается. Случайность значения приоритета немного его колеблется, поэтому в этом цикле оно идет 0, 1, 4, 11, 29.

Случайный прогон показывает что-то интересное:

TimeIt(50, RandomInsert)
LastValue = 0,748661640914465, Top.Value = 0,748661640914465, Right.Count = 0, Left.Count = 0
LastValue = 0,669427539533669, Top.Value = 0,748661640914465, Right.Count = 0, Left.Count = 1
RotateRight @value=0,669427539533669
LastValue = 0,318363281115127, Top.Value = 0,748661640914465, Right.Count = 0, Left.Count = 2
RotateRight @value=0,669427539533669
LastValue = 0,33133987678743, Top.Value = 0,748661640914465, Right.Count = 0, Left.Count = 3
RotateLeft @value=0,748661640914465
LastValue = 0,955126694382693, Top.Value = 0,955126694382693, Right.Count = 0, Left.Count = 4
RotateRight @value=0,669427539533669
RotateLeft @value=0,33133987678743
RotateLeft @value=0,318363281115127
RotateRight @value=0,748661640914465
RotateRight @value=0,955126694382693
LastValue = 0,641024029180884, Top.Value = 0,641024029180884, Right.Count = 3, Left.Count = 2
LastValue = 0,20709771951991, Top.Value = 0,641024029180884, Right.Count = 3, Left.Count = 3
LastValue = 0,830862050331599, Top.Value = 0,641024029180884, Right.Count = 4, Left.Count = 3
RotateRight @value=0,20709771951991
RotateRight @value=0,318363281115127
LastValue = 0,203250563798123, Top.Value = 0,641024029180884, Right.Count = 4, Left.Count = 4
RotateLeft @value=0,669427539533669
RotateRight @value=0,748661640914465
RotateRight @value=0,955126694382693
LastValue = 0,701743399585478, Top.Value = 0,641024029180884, Right.Count = 5, Left.Count = 4
RotateLeft @value=0,669427539533669
RotateRight @value=0,701743399585478
RotateLeft @value=0,641024029180884
LastValue = 0,675667521858433, Top.Value = 0,675667521858433, Right.Count = 4, Left.Count = 6
RotateLeft @value=0,33133987678743
RotateLeft @value=0,318363281115127
RotateLeft @value=0,203250563798123
LastValue = 0,531275219531392, Top.Value = 0,675667521858433, Right.Count = 4, Left.Count = 7
RotateRight @value=0,748661640914465
RotateRight @value=0,955126694382693
RotateLeft @value=0,701743399585478
LastValue = 0,704049674190604, Top.Value = 0,675667521858433, Right.Count = 5, Left.Count = 7
RotateRight @value=0,203250563798123
RotateRight @value=0,531275219531392
RotateRight @value=0,641024029180884
RotateRight @value=0,675667521858433
LastValue = 0,161392807104342, Top.Value = 0,161392807104342, Right.Count = 13, Left.Count = 0
RotateRight @value=0,203250563798123
RotateRight @value=0,531275219531392
RotateRight @value=0,641024029180884
RotateRight @value=0,675667521858433
RotateLeft @value=0,161392807104342
LastValue = 0,167598206162266, Top.Value = 0,167598206162266, Right.Count = 13, Left.Count = 1
LastValue = 0,154996359793002, Top.Value = 0,167598206162266, Right.Count = 13, Left.Count = 2
RotateLeft @value=0,33133987678743
LastValue = 0,431767346538495, Top.Value = 0,167598206162266, Right.Count = 14, Left.Count = 2
RotateRight @value=0,203250563798123
RotateRight @value=0,531275219531392
RotateRight @value=0,641024029180884
RotateRight @value=0,675667521858433
RotateLeft @value=0,167598206162266
LastValue = 0,173774613614089, Top.Value = 0,173774613614089, Right.Count = 14, Left.Count = 3
RotateRight @value=0,830862050331599
LastValue = 0,76559642412029, Top.Value = 0,173774613614089, Right.Count = 15, Left.Count = 3
RotateRight @value=0,76559642412029
RotateLeft @value=0,748661640914465
RotateRight @value=0,955126694382693
RotateLeft @value=0,704049674190604
RotateLeft @value=0,675667521858433
LastValue = 0,75742144871383, Top.Value = 0,173774613614089, Right.Count = 16, Left.Count = 3
LastValue = 0,346844367844446, Top.Value = 0,173774613614089, Right.Count = 17, Left.Count = 3
RotateRight @value=0,830862050331599
LastValue = 0,787565814232251, Top.Value = 0,173774613614089, Right.Count = 18, Left.Count = 3
LastValue = 0,734950566540915, Top.Value = 0,173774613614089, Right.Count = 19, Left.Count = 3
RotateLeft @value=0,20709771951991
RotateRight @value=0,318363281115127
RotateLeft @value=0,203250563798123
RotateRight @value=0,531275219531392
RotateRight @value=0,641024029180884
RotateRight @value=0,675667521858433
RotateRight @value=0,75742144871383
RotateLeft @value=0,173774613614089
LastValue = 0,236504829598826, Top.Value = 0,236504829598826, Right.Count = 17, Left.Count = 6
RotateLeft @value=0,830862050331599
RotateLeft @value=0,787565814232251
RotateLeft @value=0,76559642412029
RotateRight @value=0,955126694382693
LastValue = 0,895606500048007, Top.Value = 0,236504829598826, Right.Count = 18, Left.Count = 6
LastValue = 0,599106418713511, Top.Value = 0,236504829598826, Right.Count = 19, Left.Count = 6
LastValue = 0,8182332901369, Top.Value = 0,236504829598826, Right.Count = 20, Left.Count = 6
RotateRight @value=0,734950566540915
LastValue = 0,704216948572647, Top.Value = 0,236504829598826, Right.Count = 21, Left.Count = 6
RotateLeft @value=0,346844367844446
RotateLeft @value=0,33133987678743
RotateRight @value=0,431767346538495
RotateLeft @value=0,318363281115127
RotateRight @value=0,531275219531392
RotateRight @value=0,641024029180884
RotateRight @value=0,675667521858433
RotateRight @value=0,75742144871383
LastValue = 0,379157059536854, Top.Value = 0,236504829598826, Right.Count = 22, Left.Count = 6
RotateLeft @value=0,431767346538495
LastValue = 0,46832062046431, Top.Value = 0,236504829598826, Right.Count = 23, Left.Count = 6
RotateRight @value=0,154996359793002
LastValue = 0,0999000217299443, Top.Value = 0,236504829598826, Right.Count = 23, Left.Count = 7
RotateLeft @value=0,20709771951991
LastValue = 0,229543754006524, Top.Value = 0,236504829598826, Right.Count = 23, Left.Count = 8
RotateRight @value=0,8182332901369
LastValue = 0,80358425984326, Top.Value = 0,236504829598826, Right.Count = 24, Left.Count = 8
RotateRight @value=0,318363281115127
LastValue = 0,259324726769386, Top.Value = 0,236504829598826, Right.Count = 25, Left.Count = 8
RotateRight @value=0,318363281115127
LastValue = 0,307835293145774, Top.Value = 0,236504829598826, Right.Count = 26, Left.Count = 8
RotateLeft @value=0,431767346538495
LastValue = 0,453910283024381, Top.Value = 0,236504829598826, Right.Count = 27, Left.Count = 8
RotateLeft @value=0,830862050331599
LastValue = 0,868997387527021, Top.Value = 0,236504829598826, Right.Count = 28, Left.Count = 8
RotateLeft @value=0,20709771951991
RotateRight @value=0,229543754006524
RotateLeft @value=0,203250563798123
LastValue = 0,218358597354199, Top.Value = 0,236504829598826, Right.Count = 28, Left.Count = 9
RotateRight @value=0,0999000217299443
RotateRight @value=0,161392807104342
LastValue = 0,0642934488431986, Top.Value = 0,236504829598826, Right.Count = 28, Left.Count = 10
RotateRight @value=0,154996359793002
RotateLeft @value=0,0999000217299443
LastValue = 0,148295871982489, Top.Value = 0,236504829598826, Right.Count = 28, Left.Count = 11
LastValue = 0,217621828065078, Top.Value = 0,236504829598826, Right.Count = 28, Left.Count = 12
RotateRight @value=0,599106418713511
LastValue = 0,553135806020878, Top.Value = 0,236504829598826, Right.Count = 29, Left.Count = 12
LastValue = 0,982277666210326, Top.Value = 0,236504829598826, Right.Count = 30, Left.Count = 12
RotateRight @value=0,8182332901369
LastValue = 0,803671114520948, Top.Value = 0,236504829598826, Right.Count = 31, Left.Count = 12
RotateRight @value=0,203250563798123
RotateRight @value=0,218358597354199
LastValue = 0,19310415405459, Top.Value = 0,236504829598826, Right.Count = 31, Left.Count = 13
LastValue = 0,0133136604043253, Top.Value = 0,236504829598826, Right.Count = 31, Left.Count = 14
RotateLeft @value=0,46832062046431
RotateRight @value=0,531275219531392
RotateRight @value=0,641024029180884
RotateRight @value=0,675667521858433
RotateRight @value=0,75742144871383
LastValue = 0,483394719419719, Top.Value = 0,236504829598826, Right.Count = 32, Left.Count = 14
RotateLeft @value=0,431767346538495
RotateRight @value=0,453910283024381
LastValue = 0,453370328738061, Top.Value = 0,236504829598826, Right.Count = 33, Left.Count = 14
LastValue = 0,762330518459124, Top.Value = 0,236504829598826, Right.Count = 34, Left.Count = 14
LastValue = 0,699010426969738, Top.Value = 0,236504829598826, Right.Count = 35, Left.Count = 14

Повороты происходят не столько потому, что дерево не сбалансировано, но и из-за приоритетов, которые выбираются случайным образом. Например, мы получаем 4 поворота на 13-й вставке. У нас есть дерево, сбалансированное в 5/7 (что хорошо), но доберемся до 13/0! Казалось бы, использование случайных приоритетов заслуживает дальнейшего изучения. В любом случае, ясно, что случайные вставки вызывают намного больше вращений, чем упорядоченные вставки.

Answer 3

Я добавил расчет стандартного отклонения и изменил ваш тест, чтобы он выполнялся с наивысшим приоритетом (чтобы максимально уменьшить шум). Вот результаты:

Random                                   Ordered
0,2835 (stddev 0,9946)                   0,0891 (stddev 0,2372)
0,1230 (stddev 0,0086)                   0,0780 (stddev 0,0031)
0,2498 (stddev 0,0662)                   0,1694 (stddev 0,0145)
0,5136 (stddev 0,0441)                   0,3550 (stddev 0,0658)
1,1704 (stddev 0,1072)                   0,6632 (stddev 0,0856)
1,4672 (stddev 0,1090)                   0,8343 (stddev 0,1047)
3,3330 (stddev 0,2041)                   1,9272 (stddev 0,3456)
7,9822 (stddev 0,3906)                   3,7871 (stddev 0,1459)
18,4300 (stddev 0,6112)                  10,3233 (stddev 2,0247)
44,9500 (stddev 2,2935)                  22,3870 (stddev 1,7157)
110,5275 (stddev 3,7129)                 49,4085 (stddev 2,9595)
275,4345 (stddev 10,7154)                107,8442 (stddev 8,6200)
667,7310 (stddev 20,0729)                242,9779 (stddev 14,4033)

Я запустил профилировщик выборки, и вот результаты (количество раз, когда программа использовала этот метод):

Method           Random        Ordered
HeapifyRight()   1.95          5.33
get_IsEmpty()    3.16          5.49
Make()           3.28          4.92
Insert()         16.01         14.45
HeapifyLeft()    2.20          0.00

Вывод: случайное имеет довольно разумное распределение между левым и правым вращением, в то время как упорядоченный никогда не вращается влево.

Вот моя улучшенная "контрольная" программа:

    static void Main(string[] args)
    {
        Thread.CurrentThread.Priority = ThreadPriority.Highest;
        Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.RealTime;

        List<String> rndTimes = new List<String>();
        List<String> orderedTimes = new List<String>();

        rndTimes.Add(TimeIt(50, RandomInsert));
        rndTimes.Add(TimeIt(100, RandomInsert));
        rndTimes.Add(TimeIt(200, RandomInsert));
        rndTimes.Add(TimeIt(400, RandomInsert));
        rndTimes.Add(TimeIt(800, RandomInsert));
        rndTimes.Add(TimeIt(1000, RandomInsert));
        rndTimes.Add(TimeIt(2000, RandomInsert));
        rndTimes.Add(TimeIt(4000, RandomInsert));
        rndTimes.Add(TimeIt(8000, RandomInsert));
        rndTimes.Add(TimeIt(16000, RandomInsert));
        rndTimes.Add(TimeIt(32000, RandomInsert));
        rndTimes.Add(TimeIt(64000, RandomInsert));
        rndTimes.Add(TimeIt(128000, RandomInsert));
        orderedTimes.Add(TimeIt(50, OrderedInsert));
        orderedTimes.Add(TimeIt(100, OrderedInsert));
        orderedTimes.Add(TimeIt(200, OrderedInsert));
        orderedTimes.Add(TimeIt(400, OrderedInsert));
        orderedTimes.Add(TimeIt(800, OrderedInsert));
        orderedTimes.Add(TimeIt(1000, OrderedInsert));
        orderedTimes.Add(TimeIt(2000, OrderedInsert));
        orderedTimes.Add(TimeIt(4000, OrderedInsert));
        orderedTimes.Add(TimeIt(8000, OrderedInsert));
        orderedTimes.Add(TimeIt(16000, OrderedInsert));
        orderedTimes.Add(TimeIt(32000, OrderedInsert));
        orderedTimes.Add(TimeIt(64000, OrderedInsert));
        orderedTimes.Add(TimeIt(128000, OrderedInsert));
        var result = string.Join("\n", (from s in rndTimes
                        join s2 in orderedTimes
                            on rndTimes.IndexOf(s) equals orderedTimes.IndexOf(s2)
                        select String.Format("{0} \t\t {1}", s, s2)).ToArray());
        Console.WriteLine(result);
        Console.WriteLine("Done");
        Console.ReadLine();
    }

    static double StandardDeviation(List<double> doubleList)
    {
        double average = doubleList.Average();
        double sumOfDerivation = 0;
        foreach (double value in doubleList)
        {
            sumOfDerivation += (value) * (value);
        }
        double sumOfDerivationAverage = sumOfDerivation / doubleList.Count;
        return Math.Sqrt(sumOfDerivationAverage - (average * average));
    }
    static String TimeIt(int insertCount, Action<int> f)
    {
        Console.WriteLine("TimeIt({0}, {1})", insertCount, f.Method.Name);

        List<double> times = new List<double>();
        for (int i = 0; i < ITERATION_COUNT; i++)
        {
            Stopwatch sw = Stopwatch.StartNew();
            f(insertCount);
            sw.Stop();
            times.Add(sw.Elapsed.TotalMilliseconds);
        }

        return String.Format("{0:f4} (stddev {1:f4})", times.Average(), StandardDeviation(times));
    }

Answer 4

Да, это количество вращений, которое вызывает дополнительное время. Вот что я сделал:

• Удалите строки, проверяющие приоритет в HeapifyLeft а также HeapifyRight поэтому повороты всегда делаются.
• Добавил Console.WriteLine после если в RotateLeft а также RotateRight,
• Добавил Console.WriteLine в IsEmpty часть Insert метод, чтобы увидеть, что было вставлено.
• Провели тест один раз с 5 значениями каждый.

Выход:

TimeIt(5, RandomInsert)
Inserting 0.593302943554382
Inserting 0.348900582338171
RotateRight
Inserting 0.75496212381635
RotateLeft
RotateLeft
Inserting 0.438848891499848
RotateRight
RotateLeft
RotateRight
Inserting 0.357057290783644
RotateLeft
RotateRight

TimeIt(5, OrderedInsert)
Inserting 0.150707998383189
Inserting 1.58281302712057
RotateLeft
Inserting 2.23192588297274
RotateLeft
Inserting 3.30518679009061
RotateLeft
Inserting 4.32788012657682
RotateLeft

Результат: в 2 раза больше вращений на случайных данных.

Answer 5

Вы видите только разницу примерно в 2 раза. Если вы не отключили дневной свет из этого кода, это в основном шум. Большинство хорошо написанных программ, особенно те, которые связаны со структурой данных, могут легко иметь больше возможностей для улучшения, чем это. Вот пример.

Я просто запустил ваш код и сделал несколько стеков. Вот что я увидел:

Случайная вставка:

1 Insert:64 -> HeapifyLeft:81 -> RotateRight:150
1 Insert:64 -> Make:43 ->Treap:35
1 Insert:68 -> Make:43

Заказанная вставка:

1 Insert:61
1 OrderedInsert:224
1 Insert:68 -> Make:43
1 Insert:68 -> HeapifyRight:90 -> RotateLeft:107
1 Insert:68
1 Insert:68 -> Insert:55 -> IsEmpty.get:51

Это довольно небольшое количество выборок, но в случае случайного ввода это говорит о том, что Make (строка 43) потребляет большую долю времени. Вот этот код:

    private Treap<T> Make(Treap<T> left, T value, Treap<T> right, int priority)
    {
        return new Treap<T>(Comparer, left, value, right, priority);
    }

Затем я взял 20 стеков снимка кода Random Insert, чтобы лучше понять, что он делает:

1 Insert:61
4 Insert:64
3 Insert:68
2 Insert:68 -> Make:43
1 Insert:64 -> Make:43
1 Insert:68 -> Insert:57 -> Make:48 -> Make:43
2 Insert:68 -> Insert:55
1 Insert:64 -> Insert:55
1 Insert:64 -> HeapifyLeft:81 -> RotateRight:150
1 Insert:64 -> Make:43 -> Treap:35
1 Insert:68 -> HeapifyRight:90 -> RotateLeft:107 -> IsEmpty.get:51
1 Insert:68 -> HeapifyRight:88
1 Insert:61 -> AnonymousMethod:214

Это раскрывает некоторую информацию.
25% времени тратится на линию Make:43 или ее абонентов.
15% времени тратится на эту линию, а не на распознанную рутину, другими словами, на new сделать новый узел.
90% времени проводится в строках Insert:64 и 68 (которые вызывают Make и heapify.
10% времени уходит в RotateLeft и Right.
15% времени проводится в Heapify или его клиентах.

Я также сделал достаточно много шагов (на уровне источника) и пришел к выводу, что, поскольку дерево является неизменным, оно тратит много времени на создание новых узлов, потому что не хочет менять старые. Тогда старые собирают мусор, потому что никто больше не обращается к ним.

Это должно быть неэффективно.

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

Я не думаю, что вы можете ожидать, что какие-либо соображения производительности относительно алгоритмов дерева будут легко перенесены на неизменяемые деревья, потому что малейшее изменение в глубине дерева заставляет его перестраиваться на обратном пути, с высокой стоимостью в newсбор мусора.

Answer 6

Guge прав. Однако есть кое-что еще немного к этому. Я не говорю, что это самый важный фактор в этом случае - однако он есть, и с этим трудно что-либо сделать.

Для отсортированного ввода поиски, скорее всего, касаются горячих узлов в кэше. (Это в целом верно для сбалансированных деревьев, таких как деревья AVL, красно-черные деревья, B-деревья и т. Д.)

Поскольку вставки начинаются с поиска, это также влияет на производительность вставки / удаления.

Опять же, я не утверждаю, что это самый важный фактор во всех без исключения случаях. Однако он существует и, скорее всего, приведет к тому, что отсортированные входные данные всегда будут быстрее, чем случайные в этих структурах данных.

Answer 7

Aaronaught проделал действительно достойную работу, объясняя это.

Для этих двух особых случаев мне проще понять это с точки зрения длины пути вставки.

Для случайного ввода ваш путь вставки спускается к одному из листьев, а длина пути - таким образом, число поворотов - ограничивается высотой дерева.

В отсортированном случае вы идете по правому отделу позвоночника, и его длина равна длине позвоночника, которая меньше или равна высоте.

Поскольку вы вращаете узлы вдоль пути вставки, а путь вставки в этом случае является позвоночником, эти вращения всегда будут укорачивать позвоночник (что приведет к более короткому пути вставки при следующей вставке, поскольку путь вставки - это просто позвоночник и т. Д.).)

Изменить: для случайного случая путь вставки в 1,75 раза длиннее.

Answer 8

Попробуйте это: база данных на Treap.

http://code.google.com/p/treapdb/