RBTree: C-Insertion-Performance
Description
Bonjour,
Version du 15 janvier 2019: 5 implémentations.
Le but de cet article des de tester et de comparer les performances de l'insertions de nœuds dans des arbres bicolores avec quelques logiciels présentés par des sites "de bonne réputation".
Pour chaque logiciel, le zip contient un dossier correspondant qui comporte:
● Les fichiers sources nécessaires pour réaliser vos propres tests.
● Une image de l'arbre obtenue en insérant une permutation des nombres 0 à 999;
● Les mesures pour 10⁶ et 10⁷ insertions comprenant:
- temps d'exécution.
- la hauteur (Height) de l'arbre obtenu.
- la hauteur des nœuds noirs (HeightBlack) de l'arbre obtenu.
- remarques éventuelles.
La dernière implémentation ajoutée (personnelle et "optimisée") améliore les temps d'exécution de 15 à 25 %, n'utilise pas de pointeur parent dans chaque nœud, et donne un arbre bien régulier (comme les deux premières).
Ces mesures seront complétées au fur et à mesure de la présentation d'autres implémentations.
Lorsque les nœuds ne contiennent pas de pointeur parent (p. ex. dans Sedgewick), l'économie de mémoire pour le cas 10⁷ et un adressage de 64 bits, est tout de même de 80 millions d'octets !
De plus, les visualisations n'admettent rarement plus de cent ou mille nœuds.
L'important est d'introduire un grand nombre de nœuds et surtout de tester si l'arbre résultant est bien un arbre rouge et noir.
Comme je n'ai pas trouvé (sur le web) un code qui teste cela, je me permets de présenter le code HeightBlack(), d'ailleurs déjà utilisé précédemment.
J'ai vu qu'en comptants les nœuds noirs par branche (avec int HeightBlack()), on peut "facilement" contrôler la validité de l'arbre rouge et noir:
Cette routine de test semble rapide, même pour de grands arbres.
Et comme la hauteur (Height) des arbres bicolores est restreinte, je me contenterai d'une version récursive.
Tests effectués par HeightBlack() sur un arbre bicolore:
● Il est bien trié !
● Il n'y a pas de nœuds rouges consécutifs !
● Les nombres de nœuds noirs sur toutes les branches sont égaux !
Comme certains logiciels n'annulent pas une insertion "double", je me limite à insérer chaque fois une permutation aléatoire des nombres de 0 à Num-1:
Bonne lecture …
CodeS-SourceS: RBTree: A-Insertion (GitHub)
CodeS-SourceS: RBTree: A-Insertion (Sedgewick)
CodeS-SourceS: RBTree: B-Insertion (Personnelle)
CodeS-SourceS: RBTree: B-Insertion (Optimisation)
Version du 15 janvier 2019: 5 implémentations.
Le but de cet article des de tester et de comparer les performances de l'insertions de nœuds dans des arbres bicolores avec quelques logiciels présentés par des sites "de bonne réputation".
Pour chaque logiciel, le zip contient un dossier correspondant qui comporte:
● Les fichiers sources nécessaires pour réaliser vos propres tests.
● Une image de l'arbre obtenue en insérant une permutation des nombres 0 à 999;
● Les mesures pour 10⁶ et 10⁷ insertions comprenant:
- temps d'exécution.
- la hauteur (Height) de l'arbre obtenu.
- la hauteur des nœuds noirs (HeightBlack) de l'arbre obtenu.
- remarques éventuelles.
La dernière implémentation ajoutée (personnelle et "optimisée") améliore les temps d'exécution de 15 à 25 %, n'utilise pas de pointeur parent dans chaque nœud, et donne un arbre bien régulier (comme les deux premières).
Performances de temps d'insertion
Dans le tableau récapitulatif, les essais ont été faits avec un million et 10 millions de nœuds:Implémentation Nœuds Temps Height HeightBlack Remarques ¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯ ¯¯¯¯¯ ¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ GeeksforGeeks 10⁶ 831 ms 24 12 Bug insertion doubles ¯¯¯¯¯¯¯¯¯¯¯¯¯ 10⁷ 13097 ms 28 14 Bug d'initialisation corrigé GitHub 10⁶ 827 ms 24 12 ¯¯¯¯¯¯ 10⁷ 13434 ms 28 14 Sedgewick 10⁶ 915 ms 28 16 Nœuds sans pointeur parent ¯¯¯¯¯¯¯¯¯ 10⁷ 15080 ms 32 19 Arbre peu régulier Personnelle 10⁶ 705 ms 28 15 Nœuds sans pointeur parent ¯¯¯¯¯¯¯¯¯¯¯ 10⁷ 12822 ms 34 18 Arbre peu régulier Optimisation 10⁶ 634 ms 24 12 Nœuds sans pointeur parent ¯¯¯¯¯¯¯¯¯¯¯¯ 10⁷ 11175 ms 28 14
Ces mesures seront complétées au fur et à mesure de la présentation d'autres implémentations.
Lorsque les nœuds ne contiennent pas de pointeur parent (p. ex. dans Sedgewick), l'économie de mémoire pour le cas 10⁷ et un adressage de 64 bits, est tout de même de 80 millions d'octets !
Contrôle d'un arbre rouge et noir
A part pour des arbres de quelques nœuds, il est presque impossible d'en vérifier la régularité à l'aide de sa visualisation graphique.De plus, les visualisations n'admettent rarement plus de cent ou mille nœuds.
L'important est d'introduire un grand nombre de nœuds et surtout de tester si l'arbre résultant est bien un arbre rouge et noir.
Comme je n'ai pas trouvé (sur le web) un code qui teste cela, je me permets de présenter le code HeightBlack(), d'ailleurs déjà utilisé précédemment.
J'ai vu qu'en comptants les nœuds noirs par branche (avec int HeightBlack()), on peut "facilement" contrôler la validité de l'arbre rouge et noir:
int HeightBlack() { // Height of black nodes in the subtree this
int smlH=0,bigH=0;
if (sml) {
if (key <= sml->key) return -1;
if (!black && !sml->black) return -2;
smlH=sml->HeightBlack();
}
if (big) {
if (key >= big->key) return -1;
if ((!black) && (!big->black)) return -2;
bigH=big->HeightBlack();
}
if (smlH==-1 || bigH==-1) return -1; // not sorted
if (smlH==-2 || bigH==-2) return -2; // consecutive red nodes
if (smlH==-3 || bigH==-3 || smlH!=bigH) return -3;
// return -3: different number of black nodes
return smlH + ((black) ? 1 : 0);
} // return < 0: erreur !!!Connaîtriez-vous d'autres exemples de ce type de fonction ?
Cette routine de test semble rapide, même pour de grands arbres.
Et comme la hauteur (Height) des arbres bicolores est restreinte, je me contenterai d'une version récursive.
Tests effectués par HeightBlack() sur un arbre bicolore:
● Il est bien trié !
● Il n'y a pas de nœuds rouges consécutifs !
● Les nombres de nœuds noirs sur toutes les branches sont égaux !
Comme certains logiciels n'annulent pas une insertion "double", je me limite à insérer chaque fois une permutation aléatoire des nombres de 0 à Num-1:
// ...
srand(77); // initialise rand()
const int Num = 1000000;
int *Rnd=new int[Num];
for (int i=0; i<Num; ++i) Rnd[i]=i;
for (int i=Num; i>0;) {
int r=(rand()+(rand()<<15))%i; // pour i > 32767 = RAND_MAX
int e=Rnd[r]; Rnd[r]=Rnd[--i]; Rnd[i]=e;
} // Rnd[]: permutation des entiers 0 à Num-1
// ...Num = nombre le nombre de nœuds insérés. Adaptez sa valeur !
Bonne lecture …
Liens
CodeS-SourceS: RBTree: A-Insertion (GeeksforGeeks)CodeS-SourceS: RBTree: A-Insertion (GitHub)
CodeS-SourceS: RBTree: A-Insertion (Sedgewick)
CodeS-SourceS: RBTree: B-Insertion (Personnelle)
CodeS-SourceS: RBTree: B-Insertion (Optimisation)
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.