Grokking Algorithms

111 jours contre 30 millisecondes

Décodons d'abord le sigle qui revient à chaque page. Big O, noté O(...), ne mesure pas une durée, mais une vitesse de croissance : si vous doublez la taille des données, le temps fait quoi ? Trois familles suffisent pour 90 % du métier :

• O(1) : constant. La taille des données ne change rien. Lire tableau[500] est aussi rapide que tableau[5] ;
• O(n) : linéaire. Deux fois plus de données = deux fois plus de temps. Une boucle qui parcourt tout (foreach) ;
• O(log n) : logarithmique. Doubler les données n'ajoute qu'une étape. C'est la classe magique, celle de la recherche binaire ci-dessous.

Le n, c'est le nombre d'éléments. Et la règle d'or : on garde le terme qui domine quand n devient grand, sans les constantes. Une boucle de 3 milliards d'opérations et une boucle de n opérations sont toutes deux O(n) : à grande échelle, c'est la forme de la courbe qui décide, pas son coefficient.

Le livre fait sentir tout ça avec une histoire. Bob doit écrire, pour la NASA, une fonction qui cherche un nom dans une liste triée d'un milliard d'éléments. Deux méthodes s'offrent à lui :

• la recherche simple : parcourir la liste depuis le début, un par un, jusqu'au bon nom. Pire cas, le nom est le dernier : un milliard de vérifications. C'est du O(n) ;
• la recherche binaire : comme on cherche un mot dans un dictionnaire papier. On ouvre au milieu, le nom cherché est avant ou après, on jette la moitié inutile, on recommence sur ce qui reste. Combien de fois peut-on couper un milliard en deux avant qu'il ne reste qu'un seul élément ? Un milliard → 500 millions → 250 millions… et on arrive à 1 en seulement 30 coupes. Donc 30 essais, pas un de plus. C'est du O(log n).

L'erreur de Bob, celle que le livre veut casser : il se dit « la binaire, c'est genre 15 fois plus rapide ». Son cerveau raisonne en proportion, comme si les deux méthodes étaient sur la même courbe à des vitesses voisines. Elles ne le sont pas : l'une fait un milliard d'opérations, l'autre en fait 30. Le vrai rapport n'est pas 15, c'est un milliard divisé par 30, soit 33 millions. Le livre le met en temps (10 ms par opération) pour le rendre palpable : la recherche simple mettrait « 11 jours ! » (p. 13), la binaire 30 millisecondes. Pour exactement le même résultat.

La morale tient en un mot : ces deux familles ne diffèrent pas un peu, elles diffèrent en nature. Et c'est pour ça qu'on les étiquette avec Big O plutôt qu'avec un chrono : O(log n) annonce « cette courbe restera plate même si les données explosent », ce qu'aucun benchmark sur une petite liste ne révélera jamais.

2Tableaux et listes chaînées : le problème du cinéma

Commençons par ce que ces deux mots veulent vraiment dire, en mémoire. La mémoire de l'ordinateur, c'est une longue rangée de cases numérotées, comme une rue d'adresses.

Un tableau range ses éléments dans des cases collées les unes aux autres. Comme il connaît l'adresse de la première case et la taille d'un élément, il calcule instantanément où est le 500ᵉ : adresse de départ + 500 × taille. Lire n'importe quelle position est donc gratuit, c'est du O(1). Le revers : pour insérer un élément au milieu, il faut que les cases restent collées, donc décaler tout ce qui suit d'un cran. Sur un gros tableau, ça coûte, c'est du O(n).

Une liste chaînée fait l'inverse : ses éléments sont éparpillés n'importe où en mémoire, et chaque élément garde l'adresse du suivant, comme une chasse au trésor où chaque indice mène au prochain. Insérer un élément ne décale rien : on réécrit juste deux adresses, c'est du O(1). Le revers : pour atteindre le 500ᵉ, il n'y a pas de calcul possible, il faut suivre les indices un par un depuis le début. Lire est donc séquentiel, c'est du O(n).

D'où la métaphore du livre : vous et cinq amis cherchez des places dans un cinéma bondé. Le tableau exige six sièges côte à côte (et tout le monde déménage si un septième ami débarque). La liste chaînée dit « séparons-nous », et chacun retient juste où s'est assis le suivant ; mais pour trouver l'ami numéro 5, on passe par les quatre premiers.

Résumé du livre : « Les tableaux permettent des lectures rapides. Les listes chaînées permettent des insertions et suppressions rapides » (p. 36). Et vous le touchez tous les jours sans le savoir : en JavaScript, push() ajoute à la fin sans rien déranger (O(1)), mais unshift() insère au début, donc décale tout le reste d'un cran (O(n)).

// O(1) : on pose à la fin, personne ne bouge
file.push(client)

// O(n) : insérer au début décale TOUT le reste d'une case
file.unshift(client)   // sur 1 million d'éléments, ça se sent

Listes Python, tableaux JS, arrays PHP : chaque structure du quotidien repose sur ce choix, fait pour vous. Savoir laquelle vous avez sous les doigts, c'est savoir quelle opération est gratuite et laquelle coûte.

3La récursion sert le programmeur, pas la machine

Une fonction récursive, c'est simplement une fonction qui s'appelle elle-même. L'idée surprend, mais elle sert à découper un gros problème en une version plus petite du même problème, jusqu'à un cas tellement petit qu'on sait y répondre directement. Le livre la réduit à deux ingrédients obligatoires :

• le cas de base : la condition d'arrêt, le plus petit cas qu'on traite sans rappeler la fonction ;
• le cas récursif : la fonction se rappelle sur un problème un cran plus petit.

Oubliez le cas de base, et la fonction ne s'arrête jamais : votre compte à rebours affiche 3, 2, 1, 0, -1, -2… à l'infini. Sur une factorielle, ça donne :

function factorielle(n) {
  if (n === 1) return 1       // cas de base : on sait répondre, on arrête
  return n * factorielle(n - 1)  // cas récursif : un cran plus petit
}

Mais où sont stockés tous ces appels en attente ? Sur la pile d'appels (la call stack), que le livre dessine comme une pile de post-its : chaque appel pose un post-it dessus (« je dois encore multiplier par 3 »), et quand le cas de base répond, on retire les post-its un par un dans l'ordre inverse. Déroulé sur factorielle(3) :

Pour un dev web, la récursion brille sur tout ce qui est imbriqué par nature : parcourir un arbre DOM, un fil de commentaires imbriqués (une réponse à une réponse à une réponse, comme sur Reddit), un JSON profond, une arborescence de fichiers. Une boucle classique s'y casse les dents ; la récursion épouse la forme du problème. D'où la citation qui clôt l'éternel débat boucle contre récursion, empruntée à Leigh Caldwell : « les boucles peuvent faire gagner en performance à votre programme. La récursion fait gagner en performance à votre programmeur. Choisissez ce qui compte le plus dans votre situation ! » (p. 41).

4Diviser pour régner : trier sans se fatiguer

Diviser pour régner (en anglais divide and conquer, ou D&C) est une stratégie, pas un algorithme précis. C'est le prolongement direct de la récursion (idée 3), en trois réflexes :

• trouver le cas trivial : le plus petit problème qu'on sait résoudre sans réfléchir (une liste de 0 ou 1 élément est déjà triée) ;
• réduire vers ce cas : couper le problème en morceaux plus petits du même genre ;
• recombiner les solutions des morceaux.

Le livre l'illustre d'abord avec un terrain agricole de 1 680 × 640 m à découper en carrés égaux les plus grands possible. On pose le plus grand carré qui tient (640 × 640), il reste une bande, on recommence sur la bande, encore et encore, jusqu'à tomber sur un terrain où la division est exacte. Réponse : des carrés de 80 × 80. Vous venez d'exécuter l'algorithme d'Euclide (le calcul du plus grand commun diviseur, vieux de 2 300 ans) sans le savoir.

Mais l'usage que vous croisez tous les jours, c'est le tri. Quicksort applique exactement les trois réflexes : on choisit un élément au hasard, le pivot ; on range à gauche tout ce qui est plus petit, à droite tout ce qui est plus grand ; puis on trie chaque côté de la même façon. Le cas trivial : un côté vide ou à un élément est déjà trié, on s'arrête.

function quicksort(liste) {
  if (liste.length < 2) return liste   // cas trivial : 0 ou 1 élément, déjà trié
  const pivot = liste[0]
  const petits = liste.slice(1).filter(x => x <= pivot)
  const grands = liste.slice(1).filter(x => x >  pivot)
  return [...quicksort(petits), pivot, ...quicksort(grands)]  // recombine
}

Le piège, que le livre démonte avec des piles d'appels : si vous prenez toujours le premier élément comme pivot et que la liste est déjà triée, chaque coupe ne retire qu'un élément, et quicksort dégénère en O(n²). La parade tient en un mot : « si vous choisissez toujours un élément au hasard comme pivot, quicksort se termine en O(n log n) en moyenne » (p. 71). En pratique vous n'écrirez jamais ce code : le .sort() de votre langage est déjà un quicksort (ou un mergesort) réglé aux petits oignons. Mais savoir ce qu'il fait dessous, c'est comprendre pourquoi trier coûte O(n log n) et pas O(n).

5La table de hachage, c'est Maggie qui connaît tous les prix

Le livre introduit O(1) avec un humain. À l'épicerie, chercher un prix dans un registre page par page est O(n) ; dans un registre trié, O(log n) (la recherche binaire de l'idée 1). Mais votre collègue Maggie a tout mémorisé : vous dites « le lait ? », elle répond « 1,49 € » instantanément, que le catalogue ait 10 ou 10 000 articles. C'est ça, le O(1) : le temps de réponse ne dépend plus de la taille.

Une table de hachage, c'est Maggie en code. Le secret est une fonction de hachage : une moulinette qui transforme une clé (du texte) en un numéro de case. On donne « lait », elle ressort par exemple 3 ; on range le prix dans la case 3 d'un tableau. Pour relire, on repasse « lait » dans la même moulinette, elle redonne 3, et on va directement à la case 3. Aucun parcours : on calcule l'adresse au lieu de la chercher. Lire, écrire, supprimer, tout est O(1) en moyenne.

// vous l'utilisez déjà tous les jours, sans voir la fonction de hachage dessous
const prix = new Map()
prix.set('lait', 1.49)   // "lait" → case interne → on y pose 1.49
prix.get('lait')        // "lait" → même case → 1.49, en O(1)

« Les tables de hachage sont probablement la structure de données complexe la plus utile que vous apprendrez » (p. 78), et vous les croisez sous mille noms : Map et Set en JS, dict en Python, array en PHP. Le livre leur donne trois métiers :

• les correspondances : associer une clé à une valeur (le DNS, qui traduit web-developpeur.com en adresse IP, est une gigantesque table de hachage) ;
• la chasse aux doublons : l'électeur qui tente de voter deux fois est démasqué en O(1) (c'est le Set qui tuait la boucle O(n²) de l'idée 1) ;
• le cache : mémoriser une réponse coûteuse la première fois pour ne plus la recalculer (Redis, OPcache, le cache HTTP du navigateur, tous des tables de hachage).

Les petites lignes du contrat : deux clés différentes peuvent tomber sur la même case (une collision), qu'on range alors en mini-liste dans cette case. Trop de collisions et le O(1) se dégrade ; c'est pourquoi le moteur surveille le taux de remplissage et agrandit le tableau quand il dépasse ~70 %.

6Le vendeur de mangues et le piano : les graphes sans peur

Un graphe, c'est juste une façon de modéliser des liens : des nœuds (des choses) reliés par des arêtes (des liens entre ces choses). Un réseau social, c'est un graphe (les gens, leurs amitiés) ; une carte routière aussi (les villes, les routes) ; le web aussi (les pages, les liens). Dès qu'on a « qui est relié à qui », on a un graphe, et deux algorithmes suffisent à en tirer l'essentiel.

Le parcours en largeur (BFS, pour breadth-first search) répond à « quel est le chemin le plus court de A à B ? ». L'exemple du livre : vous cherchez un vendeur de mangues dans votre réseau. Vous vérifiez d'abord vos amis directs (cercle 1), puis leurs amis (cercle 2), et ainsi de suite, en cercles de plus en plus larges, à l'aide d'une simple file (premier arrivé, premier servi). Le premier vendeur trouvé est forcément au cercle le plus proche : c'est pour ça que « le parcours en largeur ne trouve pas seulement un chemin de A à B, il trouve le plus court » (p. 103), le plus court en nombre de sauts.

Un détail vital : marquer les gens déjà vérifiés. Peggy peut apparaître via Alice ET via Bob ; sans marquage, on la revérifie sans fin et on boucle pour toujours. (Ce « déjà vu ? » se fait avec un Set, en O(1), idée 5.)

Dijkstra prend le relais quand les arêtes ont un poids. Compter les sauts ne suffit plus : sur une carte, le chemin avec le moins de routes n'est pas le plus court en kilomètres. L'exemple du livre est une chaîne de troc, d'un livre de musique jusqu'à un piano, en passant par posters, vinyles et batterie, chaque échange coûtant un peu d'argent. Dijkstra étend toujours le nœud le moins cher atteint jusqu'ici, et déniche le chemin total à 35 $ qu'un simple comptage de sauts aurait raté. La limite, dite par le livre : un poids négatif casse Dijkstra, « il y a un algorithme pour ça ! Il s'appelle Bellman-Ford » (p. 130).

Vous utilisez ces deux-là sans le savoir : BFS dès qu'un site propose « personnes que vous pourriez connaître » (les amis d'amis du cercle 2), et Dijkstra à chaque itinéraire Google Maps (les routes pondérées par la durée).

7Les gloutons, et le mur des problèmes NP-complets

Un algorithme glouton (en anglais greedy) suit une règle bête : à chaque étape, prendre le meilleur choix du moment, sans réfléchir à la suite, et espérer que ça donne le meilleur résultat global. Vous le faites déjà : pour rendre 88 centimes, vous attrapez la plus grosse pièce qui rentre (50), puis la plus grosse qui rentre dans ce qui reste (20), et ainsi de suite. C'est glouton, et avec nos pièces, ça tombe toujours juste.

Le piège, c'est que « ça tombe juste » n'est pas garanti. Parfois le glouton donne l'optimum exact (planifier des salles : toujours prendre le cours qui finit le plus tôt laisse le plus de place pour les suivants). Parfois il se trompe, et le livre le prouve avec son cambrioleur : un sac qui porte 35 lb, et trois objets :

• une chaîne hi-fi à 3 000 $, qui pèse 30 lb ;
• un laptop à 2 000 $, 20 lb ;
• une guitare à 1 500 $, 15 lb.

Le glouton attrape le plus cher d'abord, la chaîne hi-fi (3 000 $, 30 lb). Il ne reste que 5 lb : plus rien ne rentre. Butin : 3 000 $. Sauf que laptop + guitare (20 + 15 = 35 lb pile) valaient 3 500 $. Le meilleur choix local a raté le meilleur choix global.

Puis le livre frappe le mur : certains problèmes explosent quelle que soit votre ingéniosité. Le voyageur de commerce qui doit visiter 10 villes au plus court affronte 3 628 800 itinéraires possibles, et chaque ville ajoutée multiplie ce compte. Ces problèmes portent un nom, NP-complets : aucune méthode connue ne les résout vite quand la taille grandit, on ne sait que tester un nombre de combinaisons qui explose. Le conseil du livre est libérateur : pour eux, arrêtez de chercher la solution parfaite, prenez une approximation gloutonne « assez bonne » et passez à autre chose. Savoir reconnaître un mur et cesser d'optimiser est une compétence en soi.

8La programmation dynamique : une grille, pas une formule

La programmation dynamique (DP) est la réponse propre au piège du glouton de l'idée 7. Son principe : au lieu d'attraper le meilleur objet sur le moment, on découpe le gros problème en une foule de sous-problèmes minuscules (« quel est le meilleur butin si je n'avais qu'un sac de 1 lb ? de 2 lb ? de 3 lb ? »), on résout chacun une seule fois, et on range les réponses dans une grille qu'on remplit de proche en proche. Chaque case s'appuie sur des cases déjà calculées : pas de recalcul, pas de combinaison oubliée.

Reprenons le cambrioleur, mais avec un sac de 4 lb et trois objets : une guitare à 1 500 $ (1 lb), une chaîne hi-fi à 3 000 $ (4 lb), un laptop à 2 000 $ (3 lb). On dresse une grille : une ligne par objet, une colonne par capacité de sac de 1 à 4 lb. Chaque case répond à une question précise : « avec seulement les objets vus jusqu'à cette ligne, et un sac de cette capacité, quel est le meilleur butin ? ». On remplit ligne par ligne, et la réponse finale émerge dans la dernière case, en bas à droite.

L'avertissement honnête qui en fait la meilleure introduction à la DP du marché : « il n'y a pas de formule unique pour calculer une solution de programmation dynamique » (p. 186). On conçoit la grille problème par problème. La même technique compare ensuite des chaînes (plus longue sous-chaîne commune : la faute de frappe « hish » est plus proche de « fish » que de « vista »), et c'est là-dessus que reposent git diff et les correcteurs orthographiques.