Solutions du TD-1, recherche en table

1 Liste des prénoms

Voici le programme solution. La fonction d'insertion est une insertion simple en table triée, suffisante pour le nombre somme toute réduit d'élèves de l'école.

L'algorithme à employer est décrit : ``insertion successive des prénoms'', il est même précisé que la table contient les prenoms triés.

Bon mais qu'est-ce qu'une table ? Une table est un tableau de chaîne (table) et un entier (next) qui indique la prochaine place libre dans la table.

Bon, comment insérer dans une table triée ? On part d'un squelette

  static void insertion(String nom) {

  }

Pour insérer dans la table le plus simple est de la parcourir, donc une boucle ``for'' :

static void insertion(String nom) {

   for (int i=0 ; i < next ; i++) {
     ...
  }
}

Ainsi, dans le corps de la boucle, on a i qui pointe dans la table à coup sûr. On ne s'en préocupera donc plus.

On va comparer nom à chaque élément de la table, jusqu'à arriver à trois situations différentes :

nom est déjà dans la table.
Il y a un prénom plus grand que nom dans la table.
On sort de la table.

Dans le premier cas, il n'y a pas lieu de poursuivre le parcours. En effet, la table est une table des prénoms différents.

static void insertion(String nom) {

  for (int i=0 ; i < next ; i++) {
    int r = nom.compareTo(table[i]);
    if (r == 0)
      return;
     ....
  }
}

Le plus simple est de retourner immédiatement de la méthode insertion par l'instruction return.

Dans le deuxième cas, on est certain que nom n'est pas dans la table et on vient de trouver sa place (car la table est triée), il faut donc l'insérer. Ensuite on retournera de insertion comme dans le cas précédent :

static void insertion(String nom) {

  for (int i=0 ; i < next ; i++) {
    int r = nom.compareTo(table[i]);
    if (r == 0)
      return;
    else if (r < 0) {
       for (int j=next ; j > i ; j--) // Décaler la fin de la table
         table[j] = table[j-1];
       table[i] = nom;                // Mettre nom à sa place
       next++;                        // Un elt de plus dans la table
       return;                        // Fini pour ce nom
    }
  }
  ...
}

L'écriture de la boucle est terminée. En effet, si on a ni ``r == 0'', ni ``r > 0'', alors on a forcément ``r < 0'' c'est à dire que nom est plus petit que table[i] et que l'on peut passer à l'itération suivante.

Par conséquent, lorsque la table a été complètement parcourue, on est sûr que nom est strictement plus grand que tous les éléments de la table. Il faut donc l'insérer en fin de table :

static void insertion(String nom) {

  for (int i=0 ; i < next ; i++) {
    int r = nom.compareTo(table[i]);
    if (r == 0)
      return;
    else if (r < 0) {
       for (int j=next ; j > i ; j--) // Décaler la fin de la table
         table[j] = table[j-1];
       table[i] = nom;                // Mettre nom à sa place
       next++;                        // Un elt de plus dans la table
       return;                        // Fini pour ce nom
    }
  }
  table[next] = nom;
  next++;
}

(Notons que l'insertion en fin de table s'applique notamment lorsque la table est vide.)

Voila c'est tout. La fonction insertion présentée est relativement concise et simple. Remarquez en particulier :

La comparaisons de chaînes entre nom et table[i] n'est effectuée qu'une fois et son résultat est sauvé dans une variable r, comme dans la description de la comparaison de chaînes de l'énoncé.
Le cas r > 0 peut être complètement omis, en tenant compte des comparaisons précédentes et en utilisant else.

2 Statistique des prénoms

2.1 Table des compteurs

Voici le source de notre classe Counter. Le choix de la fonction de hachage est critique pour l'efficacité. Il faut, autant que possible, que des prénoms différents donnent des clés de hachage différentes. (Sinon, on se retrouve avec une recherche linéaire dans une table non-triée).

Notre fonction est simple, elle additionne les codes des lettres des prénoms, en décalant d'un cran vers la gauche à chaque fois. Compte-tenu d'éventuels débordements de capacité, le résultat peut être négatif. On rend donc la valeur absolue de result sans se poser plus de questions.

  private static int hash (String s) {
        int result = 0;

        for (int i = 0 ; i < s.length() ; i++) {
            result *= 2;
            result += s.charAt(i);
        }
        return Math.abs (result);     
    }

Cette fonction hash suffit pour nos quelques prénoms. Si on écrivait une table de hachage pour des données plus générales, il faudrait probablement travailler plus.

Ensuite, la transformation d'une chaîne en un index de table demande de comparer la clé à trouver avec les clés de la table, jusqu'à la trouver elle ou une place libre. C'est le travail de la methode privée getIndex qui est appellée tant par set que par get.

private static int getIndex (String s) {

        int h = hash(s) % size;
        int i = h; // indice de debut de la recherche

        //        System.err.println("Hash for " + s + " is " + h);
        do {
            if (name[i] == null) { // une place libre
                name[i] = s;
                count[i] = 0;
                return i;
            }
            if (s.equals(name[i])) // de'ja` dans la table
                return i;
            i = (i + 1) % size;    // aller voir plus loin
        } while (i != h);
        // un tour complet n'a rien donne'
        throw new Error ("Table de hachage pleine");
    }

Ce code appelle deux commentaires un rouge et un rose:

L'objet null. Comment sait-on qu'une place est libre dans la table ? Le code ci-dessus exploite le fait que le tableau table est initialisé par l'appel de constructeur d'un tableau de chaînes new String [...] (dans la méthode init), auquel cas tous les éléments de table sont garantis égaux à l'objet nul null initiallement.
Suicide sur erreur. Lorsque la table est pleine, notre classe simplette des compteurs ne peut plus faire grand chose, elle sais tout juste que le programme ne peut plus fonctionner. Elle décide donc un suicide. Cela se fait très simplement en levant une exception à l'aide du mot-clé throw.

Les exceptions brisent le cours normal de l'exécution, ici ça revient à terminer le programme, vous en saurez plus en regardant ici. On remarquera que l'exception levée est un objet de la classe Error et que le constructeur de cette classe prend une chaîne en argument, mais cette remarque est bien banale.

2.2 Utilisation de la table

Voici le programme solution. Notez qu'il diffère peu du programme précédent. Essentiellement la méthode insertion commence par augmenter de un le compte du prénom inséré. Cette technique fonctionne lors de la toute première insertion d'un prénom, en raison de la spécification de Couter.get (String key) qui dit qu'une association de key à zéro est créée si aucune n'existe déjà.

  static void insertion(String nom) {
    // Ajuster le compteur
    Counter.set(nom,Counter.get(nom)+1);

      ...

  }

  public static void main (String [] args) {
    // Initialiser la table des compteurs
    Counter.init (Eleve.prenom.length);

  }

3 Belle statistique des prénoms

Voici le programme solution. L'insertion est maintenant réalisée par dichotomie et le tri choisi est quicksort. Voici notre fonction compare :

    static boolean compare (String s1, String s2) {
        int c1 = Counter.get(s1);
        int c2 = Counter.get(s2);

        if (c1 == c2)
            return s1.compareTo(s2) < 0;
        else
            return c1 > c2;
    }

La fonction compare renvoie true si s1 doit être affiché avant s2. C'est à dire si :

Le compte de s1 est plus grand que celui de s2.
Ou, si les comptes sont égaux, et que s1 précède s2 dans l'ordre alphabétique.

En termes savants, on parle d'ordre lexicographique sur la paire formée du compte et du prénom.

L'insertion par recherche dichotomique n'est pas évidente à programmer juste. Voici la nôtre :

  static void insertion(String nom) {

 // recherche dichotomique dans la table de 0 a` next-1
        int g=0;
        int d=next;
        int m;
        int r;

        while (d-g > 0) { // d-g est la taille de la table
            m = g+(d-g)/2; // m est dans la table
            r = nom.compareTo(table[m]);
            if (r < 0)
                d = m;
            else if (r > 0)
                g = m+1;
            else
                return; // nom est dans la table
        }
   ....

Par convention, la recherche se fait dans la table, de g à d-1, noté comme la sous-table table[g... d[). De cette façon, d-g est la longeur de la table. La boucle n'est donc exécutée que si la sous-table courante n'est pas vide et m qui est g plus la partie entière de la demi-longuer de la sous-table courante est toujours dans la table.

Correction

On compare le nom recherché nom à table[m] (qui se trouve être au milieu de la sous-table) Il y a trois cas :

Si nom est strictement plus petit que cet élément, alors, si nom est dans la table (qui est triée), il se trouve nécessairement dans table[g... m[.
Si nom est strictement plus grand que cet élément, alors il est à chercher dans table]m... d[ (qui est table[m+1... d[).
Sinon, on a trouvé nom dans la table et on peut arrêter de le chercher.

Terminaison

La longueur de la table table[g... d[ décroit strictement à chaque tour de boucle.

D'une itération de boucle à l'autre on passe de la sous-table table[g... d[ à l'une ou l'autre des sous-tables table[m+1... d[ ou table[g... m[, avec m = g + (d-g)/2. Remarquons d'abord que m est toujours strictement plus grand que g et strictement plus petit que d, sauf dans le cas d'une sous-table de taille un où m est égal à g. Or, c'est m+1 et non m qui peut être affecté à g pour le tour suivant.

Insertion

La sous-table courante finira donc par être vide si nom n'est pas déjà dans table et on pourra l'insérer. Reste à savoir où.

Il est simple de voir que les deux invariants suivants sont vrais initialement (les sous-tables concernées sont vides) et conservés par la boucle :

Tous les éléments de table[0... g[ sont plus petits que nom.
Tous les éléments de table[d... next[ sont plus grands que nom.

En sortie de boucle on a g == d, on doit donc insérer nom à l'indice g :

      // g est la place de nom dans la table

        for (int i = next ;  i > g ; i--)
            table[i] = table[i-1];
        table[g] = nom;
        next++;
    }

4 Culture

Il y a deux ans, vos prédecesseurs ont planché sur le même problème, mais en utilisant une technique bien différente.

La librairie Java contient une classe Hashtable qui réalise les tables de hachage. Voici une classe Counter qui utilise la librairie Java. Découvrez les joies de la programmation orientée object et en particulier, la classe Object des objets, la classe Integer des entiers-objets et comment on passe de l'un à l'autre (par un cast).

Ce document a été traduit de L^AT_EX par H^EV^EA.