임의의 입력보다 정렬 된 입력에서 내 트리에 삽입이 더 빠른 이유는 무엇입니까?
https://stackoverflow.com/questions/2437733
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
이제는 이진 검색 트리가 주문한 데이터보다 무작위로 선택된 데이터에서 구축하기가 더 빠르다고 들었습니다. 단순히 주문한 데이터는 트리 높이를 최소로 유지하기 위해 명시 적 재조정이 필요하기 때문입니다.
최근에 나는 불변을 구현했다 삼각, 무작위 배정을 사용하여 상대적으로 균형을 유지하는 특수 종류의 이진 검색 트리. 내가 예상했던 것과는 달리, 나는 정렬되지 않은 데이터보다 순서 데이터에서 약 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
코드에는 주문되지 않은 입력보다 비대칭 적으로 더 빠른 입력을 더 빨리 만드는 것이 없으므로 차이를 설명하기 위해 손실됩니다.
무작위 입력보다 순서 입력에서 트레프를 구축하는 것이 훨씬 빠른 이유는 무엇입니까?
해결책
자체 균형 나무가 존재합니다 고치다 비 랜덤 배포 데이터와 관련된 문제. 정의에 따르면, 그들은 균형 잡힌 BST, 특히 분류 된 입력과 관련된 최악의 성능을 크게 향상시키기 위해 약간의 최상의 성능을 상환합니다.
랜덤 데이터와 순서 데이터의 삽입이 느리게 삽입되는 것이 특징이기 때문에 실제로이 문제를 과도하게 생각하고 있습니다. 어느 균형 잡힌 나무. AVL에서 시도해 보면 동일한 결과가 표시됩니다.
카메론 최악의 경우를 강요하기 위해 우선 순위 점검을 제거하는 올바른 아이디어가있었습니다. 당신이 그렇게하고 나무를 악기로 만들면 각 삽입에 대해 얼마나 많은 재조정이 일어나고 있는지 확인할 수 있습니다. 실제로 무슨 일이 일어나고 있는지 매우 분명해집니다. 정렬 된 데이터를 삽입 할 때 나무는 항상 왼쪽으로 회전하고 루트의 오른쪽 아이는 항상 비어 있습니다. 삽입 노드에는 어린이가없고 재귀가 발생하지 않기 때문에 삽입은 항상 정확히 하나의 재조정을 초래합니다. 반면, 임의의 데이터에서 실행하면 거의 즉시 모든 인서트에서 여러 번의 재조정이 발생하는 것을보기 시작합니다. 잘.
우선 순위 확인이 다시 켜져 있으면 일반적으로 재조정이 될뿐만 아니라 저렴 더 많은 노드가 왼쪽 하위 트리로 밀려 나기 때문에 (삽입이 발생하지 않아서 나오지 않는 곳). 덜 발생합니다. 왜요? Teap에서 우선 순위가 높은 노드가 상단으로 떠 오르고, 오른쪽 회전 (오른쪽 회전이 동반되지 않음)은 모든 고 우선 순위 노드를 왼쪽 하위 트리로 밀어 넣기 시작합니다. 그 결과 확률의 고르지 않은 분포로 인해 재조정이 덜 자주 발생합니다.
당신이 재조정 코드를 지적한다면 이것이 사실임을 알 수 있습니다. 분류 및 임의의 입력 모두에 대해 거의 동일한 왼쪽 회전 수로 끝나지 만 임의의 입력은 동일한 수의 오른쪽 회전을 제공하여 두 배나 많은 양을 만듭니다. 가우스 입력은 가우스의 회전 분포를 초래해야합니다. 또한 정렬 된 입력에 대한 최상위 레벨 레 밸런스만큼 약 60-70% 만 있음을 알 수 있습니다. ~이다 놀랍게도, 다시 한 번, 그것은 분류 된 입력이 우선 순위의 자연 분포를 혼란스럽게하기 때문입니다.
삽입 루프 끝에서 전체 트리를 검사하여이를 확인할 수도 있습니다. 임의의 입력으로 우선 순위는 수준만큼 선형 적으로 감소하는 경향이 있습니다. 분류 된 입력을 사용하면 우선 순위는 바닥에서 1 ~ 2 레벨에 도달 할 때까지 매우 높아지는 경향이 있습니다.
바라건대 나는 이것을 설명하는 괜찮은 일을했기를 바랍니다 ... 그것이 너무 모호한 지 알려주세요.
다른 팁
나는 당신의 코드를 실행했고, 그것은 회전 수와 관련이 있다고 생각합니다. 순서 입력 중에는 회전 수가 최적이며 트리가 다시 회전 할 필요가 없습니다.
임의의 입력 중에 트리는 앞뒤로 회전해야 할 수도 있으므로 더 많은 회전을 수행해야합니다.
실제로 알기 위해서는 각 실행에 대한 왼쪽 및 오른쪽 회전 번호에 대한 카운터를 추가해야합니다. 당신은 아마 이것을 직접 할 수 있습니다.
업데이트:
Rotateleft와 Rotateright에 중단 점을 넣었습니다. 주문한 입력 동안 Rotateright는 사용되지 않습니다. 임의의 입력 중에 둘 다 타격을 받고 더 자주 사용되는 것 같습니다.
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
정렬 된 항목은 항상 나무의 오른쪽에 자연스럽게 추가됩니다. 오른쪽이 왼쪽보다 커지면 Rotateleft가 발생합니다. Rotateright는 결코 일어나지 않습니다. 새 상단 노드는 트리가 두 배가 될 때마다 대략 선택됩니다. 우선 순위 값의 무작위성은 그것을 약간 jitter 하므로이 실행에서 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
트리의 균형이 불균형이 아니라 무작위로 선택된 우선 순위 때문에 회전은 그다지 많이 발생합니다. 예를 들어 13 번째 삽입에서 4 개의 회전이 발생합니다. 우리는 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따라서 회전은 항상 완료됩니다. - 추가 a
Console.WriteLineif in 후RotateLeft그리고RotateRight. - 추가 a
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
이것은 꽤 적은 수의 샘플이지만, 무작위 입력의 경우 (라인 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%의 시간은 줄을 서서 43 또는 그 callees입니다.
15%의 시간은 인식 된 일상이 아니라 그 라인에서 소비됩니다. new 새 노드 만들기.
90%의 시간은 라인 삽입으로 소비됩니다.
시간의 10%는 Rotateleft와 Right에서 소비됩니다.
시간의 15%는 Heapify 또는 Callees에 소비됩니다.
나는 또한 소스 수준에서 상당한 양의 단일 스텝핑을했고, 나무가 불변이기 때문에 오래된 노드를 바꾸고 싶지 않기 때문에 많은 시간을 소비한다는 의심에 도달했습니다. 그런 다음 오래된 것들은 더 이상 그들을 언급하지 않기 때문에 쓰레기를 수집합니다.
이것은 비효율적이어야합니다.
나는 여전히 주문 숫자를 삽입하는 것이 무작위로 생성 된 숫자보다 빠른 이유에 대한 당신의 질문에 대답하지 않지만 나무가 불변이기 때문에 실제로 놀랍지 않습니다.
트리 알고리즘에 대한 성능 추론은 불변의 나무로 쉽게 이월 할 것으로 기대할 수 없다고 생각합니다. 나무의 깊은 변화로 인해 반격 할 때까지 재건되기 때문입니다. new-ing 및 쓰레기 수집.
@guge 옳다. 그러나 조금 더 작은 것이 있습니다. 나는 그것이이 경우에 가장 큰 요인이라고 말하지는 않지만, 거기에 있고 그것에 대해 아무것도하기가 어렵습니다.
정렬 된 입력의 경우 조회는 캐시에서 뜨거운 노드를 터치 할 수 있습니다. (이것은 일반적으로 AVL 나무, 붉은 검은 나무, B- 트리 등과 같은 균형 잡힌 나무에 해당됩니다).
인서트는 조회로 시작하므로 인서트/삭제 성능에도 영향을 미칩니다.
다시 말하지만, 나는 그것이 모든 경우에서 가장 중요한 요소라고 주장하지 않습니다. 그러나이 데이터 구조의 임의의 입력보다 항상 입력이 더 빠를 수 있습니다.
Aaronaught 이것을 설명하는 정말 괜찮은 일을했습니다.
이 두 특별한 경우, 삽입 경로 길이 측면에서 이해하기가 더 쉽습니다.
임의의 입력의 경우 삽입 경로는 잎 중 하나로 내려가 경로의 길이 (회전 수)가 나무의 높이에 의해 제한됩니다.
분류 된 경우, 당신은 오른쪽 척추 삼각형과 경계의 길이는 척추의 길이이며, 이는 높이보다 작거나 동일합니다.
이 경우 삽입 경로를 따라 노드를 회전시키고 삽입 경로는 척추이기 때문에 이러한 회전은 항상 척추를 단축시킵니다 (삽입 경로가 척추 등이므로 다음 삽입에서 더 짧은 삽입 경로가 발생합니다. )
편집 : 임의의 경우 삽입 경로는 1.75 배 더 길다.
이것을 시도하십시오 : Treap의 데이터베이스.
제휴하지 않습니다 StackOverflow
