Probleme – Le tableau associatif : un contrat, deux réalisations

1. Le contrat.

Invariant : une clé apparaît au plus une fois. C'est lui qui donne son sens au mot « associatif », et c'est ecrire qui en est responsable — d'où la nécessité de chercher avant d'ajouter.

2. Les deux réalisations.

/* (a) Liste d'associations : on cherche, on modifie ou on ajoute en tete. */
typedef struct assoc_s { int cle; int val; struct assoc_s* suiv; } assoc;

assoc* ecrire(assoc* t, int c, int v) {
    for (assoc* m = t; m != NULL; m = m->suiv) {
        if (m->cle == c) { m->val = v; return t; }     /* deja la */
    }
    assoc* n = malloc(sizeof(assoc));
    n->cle = c; n->val = v; n->suiv = t;
    return n;
}

/* (b) Tableaux paralleles TRIES par cle, recherche par dichotomie.
   INVARIANT : cles[0] < cles[1] < ... < cles[n-1]. */
typedef struct { int* cles; int* vals; int n; int cap; } tabtri;

int place(const tabtri* t, int c) {        /* premier i tel que cles[i] >= c */
    int g = 0, d = t->n;
    while (g < d) {
        int m = g + (d - g) / 2;
        if (t->cles[m] < c) { g = m + 1; } else { d = m; }
    }
    return g;
}
void ecrire(tabtri* t, int c, int v) {
    int i = place(t, c);
    if (i < t->n && t->cles[i] == c) { t->vals[i] = v; return; }
    assert(t->n < t->cap);
    for (int j = t->n; j > i; j = j - 1) {           /* on ouvre le trou */
        t->cles[j] = t->cles[j-1]; t->vals[j] = t->vals[j-1];
    }
    t->cles[i] = c; t->vals[i] = v; t->n = t->n + 1;
}

Noter que place est écrite pour rendre le point d'insertion même quand la clé est absente : une seule fonction sert à la lecture et à l'écriture, et la propriété « premier indice de clé $\ge c$ » est son invariant de sortie.

3. Le compte et la mesure. On compte les sondes, c'est-à-dire les comparaisons de clés.

n = 8000, cles deux a deux distinctes
  liste  : 31 996 000 sondes a l'ecriture, 32 004 000 a la lecture
  trie   :     92 633 sondes a l'ecriture,    103 810 a la lecture
  repere : n(n-1)/2 = 31 996 000            n log2 n = 103 726

La liste donne exactement $n(n-1)/2$ sondes à l'écriture : chaque insertion parcourt tout ce qui précède, puisque aucune clé n'est déjà là. Le tableau trié donne $103810$ sondes en lecture pour un repère théorique de $103726$ : la dichotomie tient sa promesse à $0,1\%$ près.

4. Pourquoi aucune des deux ne convient.

Le tableau trié cache un $\Theta (n)$ dans son écriture, et c'est le point du problème : la dichotomie trouve la place en $\Theta (\log n)$, mais l'insertion décale ensuite $\Theta (n)$ cases. Compter les seules sondes le masque complètement — c'est pourquoi on ne mesure jamais une seule grandeur.

Il faut donc une structure où la recherche et l'insertion soient sous-linéaires. Deux réponses, et le livre les donne toutes les deux :

• la table de hachage (chapitre chap:hachage), $O(1)$ en moyenne pour les deux, au prix de l'ordre : on ne peut plus parcourir les clés triées ;
• l'arbre binaire de recherche équilibré (chapitre chap:tas), $O(\log n)$ garanti pour les deux, en conservant l'ordre.

Et c'est bien la thèse du chapitre précédent : le contrat n'a pas bougé d'une ligne entre les quatre réalisations. Ce qui change, c'est ce qu'on peut se permettre de répéter.