ArbreAVL: C-Insertion-Performance

Télécharger le projet
Commenter

Description

Bonjour,

Version du 31 janvier 2019: 3 implémentations.
Version du  4 février 2019: 4 implémentations.
Version du  9 février 2019: 5 implémentations.
Version du 14 février 2019: 6 implémentations.
Version du 18 février 2019: 7 implémentations.
Version du 13 mars 2019: 8 implémentations.

Le but de cet article des de tester et de comparer les performances de l'insertion de nœuds dans des arbres AVL 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.
    - remarques éventuelles.
 

Performances de temps d'insertion

Dans le tableau récapitulatif, les essais ont été faits (en 64 bits) avec un million et 10 millions de nœuds: 
Implémentation     Nœuds   Temps   Height   Remarques
¯¯¯¯¯¯¯¯¯¯¯¯¯¯     ¯¯¯¯¯   ¯¯¯¯¯   ¯¯¯¯¯¯   ¯¯¯¯¯¯¯¯¯

GeeksforGeeks       10⁶    926 ms    24     Trop de mémoire en 64 bits
¯¯¯¯¯¯¯¯¯¯¯¯¯       10⁷  15148 ms    28     

GitHub              10⁶    995 ms    24     Trop de mémoire en 64 bits
¯¯¯¯¯¯              10⁷  16682 ms    28

TheCrazyProgrammer  10⁶    935 ms    24     Trop de mémoire en 64 bits
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯  10⁷  15399 ms    28

Classique           10⁶    935 ms    24     Trop de mémoire en 64 bits
¯¯¯¯¯¯¯¯¯           10⁷  15623 ms    28

Amélioré            10⁶    817 ms    24     Quatre améliorations
¯¯¯¯¯¯¯¯            10⁷  14474 ms    28

AmélioréBis         10⁶    839 ms    24     Sans "rotations"
¯¯¯¯¯¯¯¯¯¯¯         10⁷  14357 ms    28

Personnelle         10⁶    761 ms    24     Sans "rotations", incrémentations
¯¯¯¯¯¯¯¯¯¯¯         10⁷  13340 ms    28

PersonnelleBis      10⁶    606 ms    24     Itérative, retourne le nœud crée,
¯¯¯¯¯¯¯¯¯¯¯¯¯¯      10⁷  10942 ms    28     utilise la différence des hauteurs

Ces mesures seront complétées au fur et à mesure de la présentation d'autres implémentations.

Les résultats avec une compilation 32 bits sont un peu meilleurs !

A ma grande surprise, les temps de calcul des insertions AVL sont un peu plus grands que ceux des arbres rouge et noir, alors que je m'attendais plutôt à un résultat contraire.
(Sauf pour la toute dernière version PersonnelleBis !)
 

Contrôle d'un arbre AVL

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 AVL.
Comme je n'ai pas trouvé (sur le web) un code qui teste cela, je me permets de présenter le code Height(), d'ailleurs déjà utilisé précédemment.
 
En comptants les nœuds par branche (avec int Height()), on peut "facilement" contrôler la validité de l'arbre AVL.
Méthode des "hauteurs": 
  int Height() { // Height ans test
    int leftH = 0, rightH = 0;
    if (left) {
      if (data <= left->data) return -1;
      leftH = left->Height();
    }
    if (right) {
      if (data >= right->data) return -1;
      rightH = right->Height();
    }
    if (leftH == -1 || rightH == -1) return -1; // not sorted
    int d = rightH-leftH; // return -2: difference too big
    if (leftH == -2 || rightH == -2 || d < -1 || d > 1) return -2;
    int h=1+MAX(leftH, rightH); // return -3: height wrong
    if (leftH == -3 || rightH == -3 || height != h) return -3;
    return h;
  } // return < 0: erreur !!!

Méthode des "différences des hauteurs des enfants":
  int Height() { // Height and test
    int smlH = 0, bigH = 0;
    if (sml) {
      if (key <= sml->key) return -1;
      smlH = sml->Height();
    }
    if (big) {
      if (key >= big->key) return -1;
      bigH = big->Height();
    }
    if (smlH == -1 || bigH == -1) return -1; // not sorted
    int d = bigH-smlH; // return -2: difference too big
    if (smlH == -2 || bigH == -2 || d < -1 || d > 1) return -2;
    if (smlH == -3 || bigH == -3 || dif != d) return -3; // dif wrong
    return max(smlH, bigH) + 1;
  }
Ces routines de test semblent rapides, même pour de grands arbres.
Et comme la hauteur (Height) des arbres AVL est restreinte, je me contenterai de versions récursives.

Finalement, j'ai trouvé dans Sedgewick: AVLTreeST.java un test sérieux des arbres AVL, mais écrit en Java.

Tests effectués par Height() sur un arbre AVL:
● Il est bien trié !
● La différence (abs) des hauteurs au max est 1 !
● Les hauteurs correspondent !
 
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: ArbreAVL: A-Insertion (GeeksforGeeks)
CodeS-SourceS: ArbreAVL: A-Insertion (GitHub)
CodeS-SourceS: ArbreAVL: A-Insertion TheCrazyProgrammer)
CodeS-SourceS: ArbreAVL: B-Insertion (Classique)
CodeS-SourceS: ArbreAVL: B-Insertion (Amélioré)
CodeS-SourceS: ArbreAVL: B-Insertion (Amélioré Bis)
CodeS-SourceS: ArbreAVL: B-Insertion (Personnelle)
CodeS-SourceS: ArbreAVL: B-Insertion (Personnelle Bis)
CodeS-SourceS: RBTree: C-Insertion-Performance
Sedgewick: AVLTreeST.java
 
Télécharger le projet

Codes Sources

S'inscrire maintenant

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.

Du même auteur (William VOIROL)