RBTree: C-Insertion-Performance

Soyez le premier à donner votre avis sur cette source.

Vue 720 fois - Téléchargée 45 fois

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).
 

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)
 

Codes Sources

A voir également

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.