Structures de données et coût des opérations

Un cahier de clients

Awa tient une boutique à Bonamoussadi et note ses clients dans un cahier : un nom, un numéro de téléphone par ligne, dans l'ordre où ils sont venus. Pour retrouver un numéro, elle lit ligne après ligne. Avec 50 clients, c'est supportable. Avec 10 000, il lui faudra en moyenne 5 000 lignes et, au pire, les 10 000. Si elle avait tenu son cahier par ordre alphabétique, elle l'ouvrirait au milieu, verrait que le nom cherché est avant ou après, et ne garderait que la bonne moitié — comme on cherche un mot dans un dictionnaire. Même cahier, même contenu : la façon de le ranger change tout.

Le vocabulaire du coût

On mesure le coût d'une opération en nombre d'étapes élémentaires (une comparaison, une lecture) en fonction du nombre n d'éléments. Trois opérations reviennent partout :

• la recherche (lookup) : retrouver un élément donné ;
• l'insertion : ajouter un élément ;
• le parcours (traversal) : visiter tous les éléments, par exemple pour tout afficher. Il coûte au minimum n étapes, quelle que soit la structure : on ne peut pas visiter n éléments en moins de n visites.

On note l'ordre de grandeur avec la notation « grand O » : O(n) veut dire « le coût croît proportionnellement à n », O(log n) « le coût croît comme le nombre de fois qu'on peut diviser n par 2 », O(1) « le coût ne dépend pas de n ». Cette notation ignore volontairement les constantes (« 3n » et « n » sont tous deux O(n)) ; nous y reviendrons dans la dernière leçon.

Le parcours séquentiel

Parcourir dans l'ordre, jusqu'à trouver ou jusqu'à épuiser la liste. Au pire (l'élément est absent ou en dernière position), il faut n comparaisons.

La recherche dichotomique

Elle exige un tableau trié. On compare la cible à l'élément du milieu ; selon le résultat on garde la moitié gauche ou droite, et on recommence.

def binary_search(items, target):
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        if items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return None

Remarque : Python n'a pas de comparaison à trois issues, et ce code en fait jusqu'à deux par étape (== puis <). Dans ce cours on compte une comparaison à trois issues par étape (comme le comparateur d'un tri en C, qui rend un nombre négatif, nul ou positif) : c'est la convention du tableau ci-dessous.

Exemple suivi. Tableau trié [3, 8, 14, 21, 29, 35, 42], cible 35. Premier milieu : indice 3, valeur 21 ; 21 < 35, on garde la droite (indices 4 à 6). Nouveau milieu : indice 5, valeur 35 : trouvé en 2 étapes, au lieu de 6 pour un parcours.

Pourquoi si peu ? À chaque étape il reste au plus la moitié des candidats : après k étapes, au plus n ÷ 2^k. On a fini quand il n'en reste qu'un, donc après environ log₂ n étapes. Dans la convention de comptage de ce cours, on compte une comparaison à trois issues (égal, plus petit, plus grand) par étape, soit au pire ⌊log₂ n⌋ + 1 étapes :

Multiplier n par 1 000 multiplie le parcours par 1 000, mais n'ajoute qu'une dizaine d'étapes à la dichotomie. Voilà ce qu'on appelle « passer à l'échelle ».

Ce que cela ne garantit pas

• La dichotomie ne marche que sur des données triées. Trier coûte lui-même environ n × log₂ n comparaisons. Pour une seule recherche dans 50 000 éléments en désordre, trier d'abord coûte bien plus cher qu'un parcours : ce n'est rentable que si l'on cherche souvent.
• Garder un tableau trié a un prix à chaque insertion (leçon 2).
• Le « pire cas » n'est pas le cas moyen : un parcours trouve en moyenne vers n ÷ 2 si l'élément est présent. Et les constantes cachées comptent pour de petits n : sur dix éléments, le plus simple est souvent le plus rapide.

À retenir

Compter les étapes en fonction de n : parcours = n, dichotomie ≈ log₂ n (sur du trié). Un parcours complet coûte toujours au moins n. Le « pire cas » donne une garantie, pas une prédiction.

Retrouver un client sans lire le cahier

Dans la leçon précédente, même avec la dichotomie, Awa doit encore trier son cahier et le garder trié. Et si elle pouvait aller directement à la bonne page, comme dans un casier numéroté où chaque client a son tiroir ? C'est l'idée de la table de hachage. Pour la comprendre, partons de la structure plus simple dont elle dérive : le tableau.

Le tableau (liste Python)

Un tableau range ses éléments côte à côte en mémoire. L'élément n° i se trouve par un simple calcul d'adresse : accès par indice en O(1). En revanche :

En Python, x in ma_liste est un parcours. ma_liste.insert(0, x) décale tout. Pour une file où l'on retire à gauche, la structure collections.deque est faite pour cela.

La table de hachage (dict, set)

Une table de hachage possède un certain nombre de cases (buckets). Une fonction de hachage transforme une clé (un nom, un numéro) en nombre ; on prend ce nombre modulo le nombre de cases pour obtenir la case où ranger la clé. Retrouver la clé, c'est refaire le même calcul et aller directement à la case — sans parcourir les autres.

Exemple avec une fonction JOUET. Table de 8 cases ; la « fonction » additionne les codes des lettres, puis on prend le reste de la division par 8. (Les vraies fonctions sont bien meilleures ; celle-ci sert à voir les mécanismes.)

« Aaw » tombe dans la même case qu'« Awa » : c'est une collision. Deux clés différentes, une seule case. La solution classique, le chaînage, consiste à garder dans chaque case une petite liste : on y ajoute les nouvelles clés à la fin, et pour chercher on compare, dans l'ordre, les clés de la case. Chercher « Aaw » : on calcule la case 1, on compare avec « Awa » (non), puis « Aaw » (oui) : 2 comparaisons, au lieu de lire tout le cahier.

Tant que la fonction répartit bien les clés et que la table reste peu remplie, chaque case contient très peu de clés : recherche, insertion et suppression coûtent O(1) en moyenne. Quand la table se remplit trop, elle est agrandie et toutes les clés sont replacées : une insertion exceptionnelle coûte O(n), mais répartie sur l'ensemble elle reste O(1) « amorti ».

En Python : set(ma_liste) construit une table ; "Mba" in mon_set hache « Mba » et regarde une case. Sur un million d'éléments, la différence avec in sur une liste est celle d'un million de comparaisons contre quelques-unes.

Ce que cela ne garantit pas

• Le pire cas est O(n). Si toutes les clés tombent dans la même case, la table devient une simple liste. C'est un cas rare avec une bonne fonction de hachage… sauf si quelqu'un le provoque exprès : voir l'exercice de sécurité.
• Pas d'ordre trié. Une table de hachage ne sait pas répondre vite à « les clients entre D et K » ni « le plus petit ». (Un dict Python se souvient de l'ordre d'insertion depuis Python 3.7, mais ce n'est pas l'ordre des clés.)
• Elle coûte de la mémoire : des cases vides sont gardées en réserve.
• Le chaînage est notre modèle d'étude, pas le détail de Python. Les dict et set de CPython utilisent l'adressage ouvert (on cherche une autre case libre en cas de collision) et non une liste par case ; l'histoire du coût (O(1) en moyenne, O(n) au pire) reste la même, mais le schéma « une petite liste dans chaque case » n'est pas ce que fait Python en interne.
• Les clés doivent être immuables : si une clé change après coup, sa case n'est plus la bonne.
• Cette fonction de hachage n'a rien de cryptographique : elle ne cherche qu'à répartir. Les fonctions qui protègent des données sont l'objet de l'atelier 104.

À retenir

Tableau : accès par indice en O(1), recherche en O(n) (ou O(log n) si trié, mais insertion en O(n)). Table de hachage : recherche et insertion en O(1) en moyenne, mais sans ordre, avec un pire cas O(n) quand les clés se bousculent.

Un annuaire qui accepte les nouveaux clients

Le tableau trié cherche vite mais insère mal ; la table de hachage cherche et insère vite mais ignore l'ordre. Existe-t-il une structure qui fasse les deux — chercher en O(log n), insérer en O(log n), et rester triée ? Oui : l'arbre binaire de recherche (ABR).

Le principe

Chaque nœud contient une clé et jusqu'à deux enfants : à gauche des clés plus petites, à droite des clés plus grandes. Pour chercher, on part de la racine et, à chaque nœud, on compare : on descend à gauche ou à droite, jamais les deux.

Insérons 50, 30, 70, 20, 40, 60, 80 dans cet ordre dans un arbre vide :

50
  gauche : 30
    gauche : 20
    droite : 40
  droite : 70
    gauche : 60
    droite : 80

Chercher 60 : on compare avec 50 (60 est plus grand, on va à droite), avec 70 (plus petit, à gauche), avec 60 (trouvé) : 3 comparaisons, pour 7 clés. Un arbre de hauteur h (nombre de niveaux) se parcourt de la racine à une feuille en au plus h comparaisons. Si l'arbre est bien équilibré, h ≈ log₂ n : pour un million de clés, environ 20 niveaux.

Le parcours en ordre

Le grand avantage sur la table de hachage : visiter l'arbre « gauche, nœud, droite » (parcours en ordre) donne les clés triées : 20, 30, 40, 50, 60, 70, 80. Le coût est O(n), le minimum possible. Et une requête d'intervalle (« toutes les clés entre 35 et 65 ») descend d'abord vers 35 en O(log n), puis marche dans l'ordre jusqu'à 65 : on ne visite que ce qu'il faut. Une table de hachage devrait examiner les n clés.

Le piège : l'arbre déséquilibré

Insérons maintenant 10, 20, 30, 40, 50 — des clés déjà triées — dans un arbre vide. Chaque nouvelle clé est plus grande que toutes les précédentes et va donc toujours à droite :

10
  droite : 20
    droite : 30
      droite : 40
        droite : 50

L'arbre est devenu une liste chaînée : trouver 50 demande 5 comparaisons, et avec n clés triées, n comparaisons. La garantie en O(log n) dépend de l'équilibre. Les arbres auto-équilibrés (arbres rouge-noir, arbres AVL…) se réorganisent à l'insertion pour garder la hauteur proche de log₂ n. Les bases de données utilisent des variantes à beaucoup d'enfants par nœud, les arbres B : SQLite range ses tables et ses index dans des arbres B. Vous les retrouverez à l'atelier 103.

Comparaison des quatre structures

(k = nombre de résultats rendus.)

Ce que cela ne garantit pas

• Un ABR simple ne s'équilibre pas tout seul : tout dépend de l'ordre d'arrivée des clés.
• L'arbre est plus lent que la table de hachage pour une recherche exacte pure (log n contre ≈ 1), plus lourd à écrire, et ses nœuds éparpillés en mémoire sont moins favorables au processeur qu'un tableau contigu.
• Les « O » ne prédisent pas qui sera le plus rapide sur 100 éléments. Seule une mesure le dit (leçon 4).

À retenir

L'arbre équilibré offre recherche et insertion en O(log n) et un parcours trié : c'est ce qu'on achète en renonçant au O(1) de la table. Sans équilibrage, l'ordre d'arrivée peut le dégrader en liste.

Quelle structure pour quel travail ?

Il n'y a pas de « meilleure » structure, seulement des compromis. Pour choisir, on commence par décrire le profil d'accès : ce que le programme fait vraiment, et dans quelles proportions.

1. Quelle taille ? Combien d'éléments aujourd'hui, et dans un an ?
2. Quelles opérations dominent ? Recherche exacte, insertion, suppression, parcours complet, requête d'intervalle, « le plus petit » ?
3. L'ordre compte-t-il ? A-t-on besoin des données triées ?
4. Quelle fréquence ? Une fois par jour ou mille fois par seconde ?

Quelques cas :

Dans une blockchain, on retrouvera ces profils : retrouver un solde par adresse (recherche exacte, table de hachage), parcourir les blocs dans l'ordre (liste ordonnée), vérifier qu'une donnée appartient à un ensemble (ateliers suivants).

Mesurer au lieu d'estimer

La notation O dit comment le coût croît, pas combien de millisecondes il vaut. Deux programmes O(n) peuvent différer de dix fois. Un O(log n) peut perdre contre un O(n) sur de petits tableaux. La seule façon de savoir est de mesurer, avec méthode.

import timeit

for n in (1_000, 2_000, 4_000, 8_000):
    items = list(range(n))
    # cas défavorable : l'élément cherché est le dernier
    t = min(timeit.repeat(lambda: (n - 1) in items, number=200, repeat=5)) / 200
    print(n, round(t * 1e6, 1), "µs par appel")

Les bonnes pratiques de cette mesure :

• Chronométrer seulement l'opération, pas la construction des données.
• Répéter (ici 5 séries de 200 appels, le temps d'une série étant divisé par 200 pour obtenir celui d'un appel) et garder le minimum ou la médiane : le bruit (autres programmes, mise en cache) ne peut qu'ajouter du temps.
• Faire varier n et regarder comment le temps évolue, plutôt que de se fier à un seul point.
• Ne pas conclure à partir de très petites durées : au-dessous de quelques microsecondes, on mesure surtout le coût de l'appel.

Lire un doublement

Doublez n et regardez le rapport des temps :

Si votre prédiction (« la table de hachage ne doit pas varier ») n'est pas confirmée par la mesure, c'est la mesure qui a raison — il faut alors chercher pourquoi (collisions ? redimensionnement ? mémoire saturée ?). Si au contraire elle l'est, vous avez une preuve, pas une opinion.

Ce que cela ne garantit pas

Une mesure vaut pour ce matériel, ce jeu de données et cette version du langage. Un jeu de données aléatoire peut cacher un cas défavorable (clés triées dans un arbre non équilibré) ; un jeu de données trop petit peut cacher une croissance. Il faut donc dire sur quoi on a mesuré, et ne pas généraliser au-delà.

À retenir

Décrire le profil d'accès avant de choisir ; ne pas confondre croissance (O) et durée ; mesurer en répétant, en isolant l'opération et en faisant varier n ; lire un doublement pour deviner la croissance ; énoncer les limites de sa mesure.