Problème — Trois tableaux associatifs, chronométrés

Les trois réalisations sont : la liste de couples de List.assoc, le dictionnaire par ABR du chapitre chap:tas, et Hashtbl. Les clés sont $200000$ mots distincts d'un dictionnaire. Tout est compilé en code natif ; on mesure le temps par recherche.

1. La recherche. Mesuré :

Les trois lignes se lisent ensemble. L'écart liste/hachage est de quatre ordres de grandeur : c'est la différence entre $O(n)$ et $O(1)$ à $n=2\cdot 10^5$, et il vaudrait $10^5$ à $n=10^6$. L'écart arbre/hachage, lui, n'est que de $4,6$ : c'est un rapport constant en apparence — en réalité il croît en $\log n$, mais $\log n$ ne vaut que $17,6$ ici, et la constante du hachage, elle, comprend le calcul du haché. Un facteur $5$ ne se décide pas sur la complexité : il se décide sur ce qu'on demande d'autre à la structure.

La hauteur mesurée de l'arbre est $41$, pour un ${\log }_{2}n$ de $17,6$ : l'arbre construit dans un ordre aléatoire est haut d'un multiple constant de ${\log }_{2}n$ — ici $2,3$ fois. C'est le résultat classique sur l'ABR aléatoire : sa hauteur moyenne est $\Theta (\log n)$, sans le moindre rééquilibrage. L'équilibre explicite de l'arbre bicolore ne sert donc pas au cas moyen, il sert à supprimer le pire.

2. La construction, et l'ordre d'insertion. Mesuré sur $20000$ clés :

Un facteur $648$ pour les mêmes clés. L'arbre construit en ordre trié est le peigne annoncé par le chapitre chap:tas : $h=n-1$ exactement, et la construction est passée en $\Theta (n^2)$. La table de hachage, elle, est insensible à l'ordre d'insertion — c'est un de ses avantages que le tableau du chapitre ne mentionne pas, et il n'est pas mince : elle n'a pas de pire cas d'entrée, seulement un pire cas de clés.

3. Le listage trié. Mesuré sur les $200000$ clés :

Les deux listes obtenues sont identiques — vérifié clé par clé. Le rapport est $9$, et il croît en $\log n$ : l'arbre rend une liste déjà triée en $\Theta (n)$, la table doit trier en $\Theta (n\log n)$.

4. Le verdict. Le tableau du chapitre est confirmé sur ses quatre lignes, et la troisième — « aucun parcours trié possible » — est bien la ligne décisive : c'est la seule où l'écart est qualitatif. Sur la recherche, les trois structures diffèrent d'un facteur ; sur l'ordre, la table ne sait rien faire du tout et doit sous-traiter à un tri.

Deux nuances que la mesure ajoute, et que le tableau ne dit pas.

• Le facteur $4,6$ entre arbre et table est petit. Il ne justifie pas à lui seul de renoncer aux garanties de l'arbre, ni à son parcours trié. Une structure qui va cinq fois plus vite sur une opération et ne sait pas en faire une autre n'est pas « meilleure ».
• La ligne « pire cas » du chapitre est asymétrique. L'ABR a un pire cas d'entrée — des clés triées, ce qui arrive tous les jours —, et le mesuré le montre : facteur $648$. La table a un pire cas de clés choisies — ce qui ne survient que si un adversaire les choisit. Ces deux pires cas n'ont pas la même probabilité, et c'est ce qui décide en pratique.