Почему вставка в мое дерево выполняется быстрее при отсортированном вводе, чем при случайном вводе?
https://stackoverflow.com/questions/2437733
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Теперь я всегда слышал, что бинарные деревья поиска быстрее строятся из случайно выбранных данных, чем из упорядоченных данных, просто потому, что упорядоченные данные требуют явного перебалансирования, чтобы свести высоту дерева к минимуму.
Недавно я внедрил неизменяемый треап, особый вид бинарного дерева поиска, которое использует рандомизацию для поддержания относительной сбалансированности.В отличие от того, что я ожидал, я обнаружил, что могу последовательно создавать treap примерно в 2 раза быстрее и, как правило, лучше сбалансированно на основе упорядоченных данных, чем неупорядоченных - и я понятия не имею, почему.
Вот моя реализация treap:
А вот и тестовая программа:
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
Я не вижу в коде ничего, что делало бы упорядоченный ввод асимптотически быстрее, чем неупорядоченный, поэтому я затрудняюсь объяснить разницу.
Почему создать treap на основе упорядоченных входных данных намного быстрее, чем на основе случайных входных данных?
Решение
Самобалансирующиеся деревья существуют для того, чтобы исправить проблемы, связанные с неслучайно распределенными данными.По определению, они отказываются от части производительности в лучшем случае, чтобы значительно улучшить производительность в наихудшем случае, связанную с несбалансированными BSTS, в частности, с отсортированными входными данными.
Вы на самом деле переоцениваете эту проблему, потому что более медленная вставка случайных данных по сравнению супорядоченные данные являются характеристикой Любой сбалансированное дерево.Попробуйте это на AVL, и вы увидите те же результаты.
Кэмерон у меня была правильная идея - убрать проверку приоритета, чтобы использовать наихудший вариант.Если вы сделаете это и настроите свое дерево таким образом, чтобы видеть, сколько перебалансировок происходит для каждой вставки, на самом деле становится очень очевидно, что происходит.При вставке отсортированных данных дерево всегда поворачивается влево, а правый дочерний элемент корня всегда пуст.Вставка всегда приводит ровно к одному перебалансированию, поскольку узел вставки не имеет дочерних элементов и рекурсия не происходит.С другой стороны, когда вы запускаете его на случайных данных, почти сразу же вы начинаете видеть множественные перебалансировки, происходящие при каждой вставке, целых 5 или 6 из них в наименьшем случае (50 вставок), потому что это происходит и на поддеревьях.
Когда проверка приоритета снова включена, обычно выполняется не только перебалансировка менее дорогой из-за того, что больше узлов помещается в левое поддерево (откуда они никогда не выходят, потому что там не происходит вставок), но они также менее вероятно произойти.Почему?Потому что в treap высокоприоритетные узлы всплывают наверх, и постоянные повороты влево (не сопровождаемые поворотами вправо) также начинают выталкивать все высокоприоритетные узлы в левое поддерево.В результате перебалансировки происходят реже из-за неравномерного распределения вероятности.
Если вы воспользуетесь кодом перебалансировки, то увидите, что это правда;как для отсортированного, так и для случайного ввода вы получаете почти одинаковое количество поворотов влево, но случайный ввод также дает одинаковое количество поворотов вправо, что в целом составляет в два раза больше.Это не должно удивлять - гауссовский ввод должен приводить к гауссовскому распределению вращений.Вы также увидите, что существует только примерно на 60-70% больше перебалансировок верхнего уровня для отсортированных входных данных, что, возможно является удивительно, и опять же, это связано с тем, что упорядоченные входные данные нарушают естественное распределение приоритетов.
Вы также можете убедиться в этом, просмотрев полное дерево в конце цикла вставки.При случайном вводе приоритеты, как правило, уменьшаются довольно линейно по уровню;при отсортированных входных данных приоритеты, как правило, остаются очень высокими до тех пор, пока вы не перейдете на один или два уровня снизу.
Надеюсь, я проделал достойную работу, объясняя это...дайте мне знать, если что-то из этого будет слишком расплывчатым.
Другие советы
Я запустил ваш код, и я думаю, что это связано с количеством поворотов.При упорядоченном вводе количество поворотов является оптимальным, и дереву никогда не придется поворачиваться обратно.
Во время случайного ввода дереву придется выполнять больше вращений, потому что ему, возможно, придется вращаться взад и вперед.
Чтобы действительно выяснить это, мне пришлось бы добавить счетчики для количества поворотов влево и вправо для каждого запуска.Вероятно, вы можете сделать это сами.
Обновить:
Я поставил точки останова на rotateleft и rotateright.При упорядоченном вводе rotateright никогда не используется.При случайном вводе попадают оба параметра, и мне кажется, что они используются чаще.
ОБНОВЛЕНИЕ 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!Казалось бы, использование случайных приоритетов заслуживает дальнейшего изучения.Во всяком случае, ясно видно, что случайные вставки вызывают намного больше поворотов, чем упорядоченные вставки.
Я добавил расчет стандартного отклонения и изменил ваш тест, чтобы он выполнялся с наивысшим приоритетом (чтобы максимально уменьшить шум).Вот такие результаты:
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));
}
Да, именно количество оборотов приводит к дополнительному времени.Вот что я сделал:
- Удалите строки, проверяющие приоритет в
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 раза больше вращений для случайных данных.
Вы видите разницу всего лишь примерно в 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% времени тратится на строки Insert: 64 и 68 (которые вызывают Make и heapify .
10% времени тратится на поворот влево и вправо.
15% времени тратится на Heapify или вызываемых им пользователей.
Я также выполнил изрядное количество одношаговых операций (на уровне исходного кода) и пришел к подозрению, что, поскольку дерево является неизменяемым, оно тратит много времени на создание новых узлов, потому что не хочет менять старые.Тогда старые файлы становятся мусором, потому что на них больше никто не ссылается.
Это должно быть неэффективно.
Я все еще не отвечаю на ваш вопрос о том, почему вставка упорядоченных чисел выполняется быстрее, чем случайно сгенерированных чисел, но на самом деле это меня не удивляет, потому что дерево неизменяемо.
Я не думаю, что вы можете ожидать, что какие-либо рассуждения о производительности древовидных алгоритмов будут легко перенесены на неизменяемые деревья, потому что малейшее изменение в глубине дерева приводит к его перестройке на обратном пути с высокими затратами в new-монтаж и вывоз мусора.
@Guge это правильно.Однако в этом есть еще кое-что.Я не говорю, что это самый важный фактор в данном случае - однако он есть, и с этим трудно что-либо сделать.
Для отсортированных входных данных поисковые запросы, скорее всего, касаются горячих узлов в кэше.(Это верно в целом для сбалансированных деревьев, таких как AVL-деревья, красно-черные деревья, B-деревья и т.д.)
Поскольку вставки начинаются с поиска, это также влияет на производительность вставки / удаления.
Опять же, я не утверждаю, что это самый важный фактор во всех без исключения случаях.Однако он существует и, вероятно, приведет к тому, что отсортированные входные данные в этих структурах данных будут всегда выполняться быстрее, чем случайные.
Аарон . проделал действительно достойную работу, объясняя это.
Для этих двух особых случаев мне легче понять это с точки зрения длины пути вставки.
При случайном вводе ваш путь вставки ведет вниз к одному из листьев, а длина пути - следовательно, количество поворотов - ограничены высотой дерева.
В разобранном случае вы идете по правый позвоночник длина корешка и переплета - это длина корешка, которая меньше или равна высоте.
Поскольку вы вращаете узлы вдоль пути вставки, а вашим путем вставки в данном случае является позвоночник, эти вращения всегда будут укорачивать позвоночник (что приведет к более короткому пути вставки при следующей вставке, поскольку путь вставки - это просто позвоночник и т.д.)
Редактировать:в случайном случае путь вставки в 1,75 раза длиннее.
Попробуй это:база данных на treap.
