Portail / Le langage Vala / Les structures de données(Sommaire)

Les listes.

Mise à jour du 14/05/2022.

En informatique, on manipule principalement des structures de données construites à partir de ressources le plus souvent externes (fichier, base de données, réseau, etc.). Il existe une infini variété de structure en fonction du type de données manipulées. C'est tout l'intérêt des classes "patron" (ou classes "génériques"). L'empli de ce type de classes permet de réduire les structures manipulée à 3 grandes familles principalement encore appelées "collections" :

• les listes (list) qui sont une file d'objets que l'on peut parcourir dans les deux sens et au sein de laquelle on peut identifier un début et une fin ;
• les cartes (map) qui sont des listes mais dont chaque entrée est en plus repérée par une clef ;
• les arbres (tree) qui introduisent la notion "parent-enfants". Ces arbres, lorsque chaque nœud est limité à deux enfants sont appelés binaires dans les autres cas, ils sont appelés n-aires. Les arbres binaires sont souvent utilisés dans les index car on peut les équilibrer pour réduire leur profondeur et ainsi obtenir des règles de parcours qui répondent à une loi de forme exponentielle de base 2. Leur temps de parcours devient alors prévisible en fonction du nombre de nœuds de l'arbre.

Dans cet article nous allons nous intéresser aux listes.

Structure.

Vala met en œuvre de nombreux types de liste. Disposant de la notion de référence et de pointeurs, il connaît les liste chaînées simples, les listes chaînées double, les liste chaînées simples ou double avec identification du début et de la fin ainsi que les itérateurs permettant de les parcourir.

Si la connaissance de ces structures est utiles lorsque l'on extrait des données depuis les fonctions de bas niveau (librairies en code C), ce ne sont généralement pas celles-là que vous utilisez lorsque vous avez le choix de la structure. Dans ce cas, on utilise le plus souvent la collection ArrayList<G>. Cette classe implémente 3 interfaces : Iterable<G>, Collection<G> et List<G>.

Exemple

A partir de la classe GLib.Random, extraire un nombre donné N d'entiers (32 bits)passé en argument, les trier et enfin les afficher.

using GLib;
using Gee;

class Helper {

  public static int int32Comparator(int32 left, int32 right) {
      if (left - right < 0)
        return -1;
      return (left - right > 0) ? 1 : 0;
  }

  /**
   * Transformation d'une chaîne de caractères en un entier.
   *
   * @parameter s Chaîne à convertir.
   * @return Valeur convertie ou null si la conversion est impossible.
   */
  public static int? parseInt(string s) {
    if (s.length == 0)
      return null;
    int? result;
    string? noparse;
    if (! int.try_parse(s, out result, out noparse, 10))
      return null;
    return (noparse != null) ? result : null;
  }
}

void main(string[] args) {
  // Traitement de la ligne de commande (entier attendu).
  if (args.length <= 1) {
    stdout.printf("Vous devez transmettre un entier à ce programme.\n");
    return;
  }
  int? count = Helper.parseInt(args[1]);
  if (count == null) {
     stdout.printf("le paramètre transmis [%s] n'est pas un entier\n", args[1]);
     return;
  }
  stdout.printf(@"Nombre d'entiers à trier : $count\n", count);
  // Tirage au sort
  ArrayList list = new ArrayList();
  for (int k = 0; k < count; k++) {
    uint32 ui = GLib.Random.next_int();
    int32 i = (int32)ui;
    list.add(i);
  }
  stdout.printf("Tirage au sort achevé\n");
  // Tri
  list.sort(Helper.int32Comparator);
  // Affichage
  list.foreach((val) => {
      stdout.printf("%d\n", val);
      return true;
  });
}

La commande de génération avec information de mise au point est :

valac -g --save-temps --pkg gee-0.8

La vitesse d'exécution même pour un million d'entiers est assez bluffante.