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

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

20 голосов
/ 13 марта 2010

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

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

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

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

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

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

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

Ответы [ 8 ]

10 голосов
/ 13 марта 2010

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

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

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

UPDATE:

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

ОБНОВЛЕНИЕ 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! Казалось бы, использование случайных приоритетов заслуживает дальнейшего изучения. В любом случае, ясно, что случайные вставки вызывают гораздо больше вращений, чем упорядоченные вставки.

9 голосов
/ 14 марта 2010

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

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

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

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

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

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

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

4 голосов
/ 13 марта 2010

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

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));
    }
3 голосов
/ 13 марта 2010

Вы видите разницу только в 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 снимков с кода случайной вставки, чтобы лучше понять, что он делает: 

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% времени тратится на вставку строк: 64 и 68 (которые вызывают Make и heapify.
10% времени уходит в RotateLeft и Right.
15% времени проводится в Heapify или его клиентах.

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

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

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

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

3 голосов
/ 13 марта 2010

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

  • Удалите строки, проверяющие приоритет в HeapifyLeft и HeapifyRight, чтобы вращения всегда выполнялись.
  • Добавлено Console.WriteLine после if в 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 раза больше вращений на случайных данных.

1 голос
/ 14 марта 2010

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

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

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

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

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

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

1 голос
/ 13 марта 2010

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

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

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

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

0 голосов
/ 05 декабря 2010

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

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

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

Похожие темы

...