Pourquoi est-insertion dans mon arbre plus rapide sur l'entrée triée que l'entrée au hasard?
https://stackoverflow.com/questions/2437733
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Maintenant, je l'ai toujours entendu parler des arbres binaires de recherche sont plus rapides à construire à partir des données sélectionnées au hasard que les données ordonnées, simplement parce que les données ordonné exige un rééquilibrage explicite de garder la hauteur des arbres au minimum.
Récemment, je mis en œuvre un immuable Treap , un type particulier d'arbre binaire de recherche qui utilise à la randomisation maintenir lui-même relativement équilibrée. Contrairement à ce que je pensais, je trouve que je peux construire toujours un Treap au sujet 2x plus rapide et généralement mieux équilibrée à partir des données ordonnées que les données non ordonnée -. Et je ne sais pas pourquoi
Voici mon implémentation Treap:
Et voici un programme de test:
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());
}
}
}
}
Et voici un tableau comparant les temps d'insertion aléatoires et ordonnées en millisecondes:
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
Je ne vois rien dans le code qui rend l'entrée commandé asymptotiquement plus rapide que l'entrée non ordonnée, donc je suis à une perte pour expliquer la différence.
Pourquoi est-il tellement plus rapide de construire une Treap d'entrée ordonnée que l'entrée aléatoire?
La solution
Il existe des arbres gyropodes fix les problèmes associés à des données non aléatoire distribués. Par définition, ils font le commerce un peu loin de la meilleure performance cas d'améliorer considérablement les performances pire des cas associés à BSTS non équilibrés, en particulier celle de l'entrée triée.
Vous overthinking effectivement ce problème, car plus lent insertion par rapport à des données aléatoires ordonné des données est une caractéristique de any arbre équilibré. Essayez-le sur un AVL et vous verrez les mêmes résultats.
Cameron avait la bonne idée, en supprimant le contrôle de la priorité à donner le pire des cas. Si vous le faites et l'instrument de votre arbre afin que vous puissiez voir combien de rééquilibrages se produisent pour chaque insert, il devient en fait très évident ce qui se passe. Lors de l'insertion des données triées, l'arbre tourne toujours à gauche et droit de l'enfant de la racine est toujours vide. L'insertion résulte toujours exactement un rééquilibre car le nœud d'insertion n'a pas d'enfant et pas récursion se produit. D'autre part, lorsque vous exécutez sur les données aléatoires, presque immédiatement, vous commencez à voir plusieurs rééquilibrages qui se passe sur chaque insert, autant que 5 ou 6 d'entre eux dans le plus petit cas (50 inserts), parce qu'il se passe sur les sous-arbres comme bien.
Avec la priorité vérification rallumé, non seulement sont rééquilibre généralement moins cher en raison de plusieurs noeuds poussés dans le sous-arbre gauche (où ils viennent jamais de car aucune insertions il arrive), mais ils sont également moins susceptibles de se produire. Pourquoi? Parce que dans le Treap, les nœuds prioritaires flottent au sommet, et la gauche rotations constantes (non accompagnées de bonnes rotations) commencent à pousser tous les nœuds de haute priorité dans le sous-arbre gauche ainsi. Le résultat est que rééquilibre sont moins fréquents en raison de la répartition inégale des probabilités.
Si vous instrumenter le code de rééquilibrage, vous verrez que cela est vrai; tant pour l'entrée aléatoire et triée, vous vous retrouvez avec un nombre presque identique de tours à gauche, mais l'entrée aléatoire donne aussi le même nombre de bonnes rotations, ce qui en fait deux fois plus nombreux dans tous. Cela ne devrait pas être surprenant - entrée gaussienne devrait se traduire par une distribution gaussienne des rotations. Vous verrez aussi qu'il ya seulement environ 60-70% comme beaucoup plus haut niveau rééquilibre pour l'entrée triée, qui peut-être surprenant, et encore une fois, cela est dû à l'entrée avec le Sorted déconner naturel répartition des priorités.
Vous pouvez également vérifier en inspectant l'arbre complet à la fin d'une boucle d'insertion. Avec l'entrée aléatoire, les priorités ont tendance à diminuer en fonction du niveau assez linéaire; avec l'entrée Sorted, les priorités ont tendance à rester très élevé jusqu'à ce que vous arrivez à un ou deux niveaux à partir du bas.
Il faut espérer que je l'ai fait un bon travail pour expliquer cela ... laissez-moi savoir si tout cela est trop vague.
Autres conseils
J'ai couru votre code, et je pense qu'il a à voir avec le nombre de rotations. Lors de la saisie ordonnée, le nombre de rotations sont optimales, et l'arbre ne devra jamais tourner le dos.
Pendant l'entrée aléatoire l'arbre devra effectuer plus de rotations, car il peut avoir à tourner dans les deux sens.
Pour vraiment, je dois ajouter des compteurs pour le nombre de rotations à gauche et à droite pour chaque course. Vous pouvez probablement faire vous-même.
Mise à jour:
Je mets sur des points d'arrêt et rotateleft rotateright. Pendant rotateright d'entrée commandé est jamais utilisé. Pendant l'entrée aléatoire, les deux sont touchés, et il me semble qu'ils sont plus fréquemment utilisés.
Mise à jour 2:
I ajouté un peu de sortie à l'article 50 ordonné l'exécution (en remplaçant par des nombres entiers pour la clarté), pour en savoir plus:
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
Les articles commandés toujours ajoutés à obtient le côté droit de l'arbre, naturellement. Lorsque le côté droit devient plus grand que la gauche, un rotateleft arrive. Rotateright ne se produit jamais. Un nouveau nœud supérieur est sélectionné à peu près à chaque fois que l'arbre double. Le caractère aléatoire de la frousse de valeur de priorité un peu, il va 0, 1, 4, 11, 29 dans cette course.
Une course au hasard révèle quelque chose d'intéressant:
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
Rotations se passent pas tant parce que l'arbre est déséquilibré, mais à cause des priorités, qui sont choisis au hasard. Par exemple, nous obtenons 4 rotations à la 13e insertion. Nous avons un arbre équilibré à 5/7 (ce qui est bien), mais arrive à 13/0! Il semblerait que l'utilisation des priorités au hasard mérite une enquête plus approfondie. Quoi qu'il en soit, il est évident de voir que les inserts aléatoires causent beaucoup plus de rotations, que les inserts commandés.
J'ajouté calcul de l'écart-type, et changé votre test pour fonctionner à la plus haute priorité (pour réduire le bruit autant que possible). Ce sont les résultats:
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)
J'ai couru un profileur d'échantillonnage et voici les résultats (nombre de fois le programme était dans cette méthode):
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
Conclusion: le hasard a une répartition assez raisonnable entre la rotation gauche et à droite, alors que le fait tourner à gauche jamais commandé
.Voici mon programme amélioré "de référence":
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));
}
Oui il est le nombre de rotations qui provoque le temps supplémentaire. Voici ce que je l'ai fait:
- Supprimer les lignes de contrôle en priorité
HeapifyLeftetHeapifyRightsi les rotations sont toujours fait. - Ajout d'un
Console.WriteLineaprès siRotateLeftetRotateRight. - Ajout d'un
Console.WriteLinedans la partieIsEmptyde la méthodeInsertpour voir ce qui a été inséré. - Ran le test une fois avec 5 valeurs chacun.
Sortie:
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
Résultat: 2 fois plus de rotations sur des données aléatoires
.Vous ne voir une différence d'environ 2x. À moins que vous avez accordé les Daylights de ce code, qui est essentiellement dans le bruit. La plupart des programmes bien écrits, en particulier celles impliquant la structure de données, peut facilement avoir plus de place pour l'amélioration que cela. Voici un exemple.
Je viens de rencontrer votre code et pris quelques stackshots. Voici ce que je voyais:
Aléatoire Insérer:
1 Insert:64 -> HeapifyLeft:81 -> RotateRight:150
1 Insert:64 -> Make:43 ->Treap:35
1 Insert:68 -> Make:43
Ordonné Insérer:
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
est un nombre assez restreint d'échantillons, mais il suggère dans le cas d'entrée aléatoire Marque (ligne 43) consomme une fraction plus de temps. C'est ce code:
private Treap<T> Make(Treap<T> left, T value, Treap<T> right, int priority)
{
return new Treap<T>(Comparer, left, value, right, priority);
}
Je pris alors 20 stackshots du code d'insertion aléatoire pour obtenir une meilleure idée de ce qu'il faisait:
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
révèle quelques informations.
25% du temps est consacré à la ligne Marque: 43 ou ses
fonctions appelées.
15% du temps est consacré à cette ligne, et non pas dans une routine reconnue, autrement dit, en faisant new un nouveau nœud.
90% du temps est passé dans les lignes Insertion: 64 et 68 (qui appel émis et heapify
.
10% du temps est consacré à RotateLeft et droit.
15% du temps est consacré à Heapify ou ses fonctions appelées.
J'ai aussi fait une bonne quantité de simple pas (au niveau de la source), et est venu à soupçonner que, puisque l'arbre est immuable, il passe beaucoup de temps à faire de nouveaux nœuds, car il ne veut pas changer les vieux. Ensuite, les anciens sont des ordures collectées parce que personne ne se réfère à eux plus.
Cela doit être inefficace.
Je ne suis toujours pas répondre à votre question de savoir pourquoi l'insertion de numéros commandés est plus rapide que nombres générés au hasard, mais cela ne me surprend pas vraiment, parce que l'arbre est immuable.
Je ne pense pas que vous pouvez vous attendre un raisonnement de performance sur les algorithmes d'arbres pour transporter plus facilement aux arbres immuables, parce que le moindre changement profond dans les causes arbre à être reconstruit sur le chemin du retour, à un coût élevé en new la collecte des ordures et -ing.
@Guge est bon. Cependant, il est un peu petit peu plus à lui. Je ne dis pas qu'il est le plus grand facteur dans ce cas -. Mais il est là et il est difficile de faire quoi que ce soit à ce sujet
Pour une entrée triée, touchent probablement les recherches nœuds qui sont chauds dans le cache. (Cela est vrai en général pour les arbres équilibrés comme AVL, les arbres rouge-noir, B-arbres, etc.)
Depuis inserts commencent par une recherche, cela a un effet sur insertion / suppression performance.
Encore une fois, je ne prétends pas que c'est le facteur le plus important dans tous les cas et tous. Il est là, cependant, et entraînera probablement des entrées étant toujours triés plus rapidement que les aléatoires dans ces structures de données.
Aaronaught a fait un travail décent vraiment expliquer cela.
Pour ces deux cas particuliers, je trouve qu'il est plus facile de le saisir en termes de longueurs de trajet d'insertion.
Pour l'entrée aléatoire, votre chemin d'insertion descend à l'une des feuilles et la longueur du chemin - ainsi le nombre de rotations -. Sont limitées par la hauteur de l'arbre
Dans le cas trié, vous marchez sur
Essayez ceci:. Base de données sur Treap
