Programming Pearls

1Le coup de fil de quinze minutes (et le bitmap)

Un programmeur appelle Bentley : comment trier un fichier sur disque ? Bentley commence à esquisser un tri fusion sur disque, environ 200 lignes et une semaine de travail. Puis il pose des questions. Le fichier : au plus 10 millions de numéros de téléphone gratuits, des entiers à 7 chiffres, sans doublons, sans données associées, et « environ un mégaoctet » de mémoire libre. Soudain le problème n'est plus « trier un fichier » ; c'est « trier 10 millions de petits entiers distincts dans 1 Mo ».

La réponse : représenter les données par 10 millions de bits. Le bit i vaut 1 si le numéro i est dans le fichier. On lit l'entrée, on allume les bits, puis on parcourt le bitmap une fois et on réécrit les numéros, triés gratuitement. Quelques dizaines de lignes, quelques heures de travail, environ dix secondes d'exécution. « Le programmeur m'a exposé son problème par téléphone ; il nous a fallu environ quinze minutes pour arriver au vrai problème et trouver la solution bitmap » (Column 1). Et la morale, en une ligne : « définir le problème représentait environ quatre-vingt-dix pour cent de cette bataille ». Saint-Exupéry a le dernier mot : la perfection est atteinte quand il n'y a plus rien à retirer.

2Aha ! : le retournement de mains et la signature triée

La Column 2 collectionne les problèmes dont la solution ressemble à un tour de magie. Faire pivoter un tableau de d positions, sur place, en temps linéaire ? Renverser la première partie, renverser la seconde, renverser le tout ; terminé. Doug McIlroy le démontrait avec ses mains : retourner la main gauche, retourner la droite, retourner les deux ensemble.

Trouver toutes les familles d'anagrammes d'un dictionnaire de 230 000 mots ? La force brute est sans espoir (comparer tous les couples de mots coûte autour de 15 heures). Le aha tient en une fonction : donner à chaque mot une signature en triant ses lettres.

signature = lambda mot: "".join(sorted(mot))
signature("deposit")   # → "deiopst"
signature("dopiest")   # → "deiopst"  ← MÊME signature : ce sont des anagrammes

Il suffit alors de trier les mots par signature : les anagrammes atterrissent côte à côte. Un pipeline Unix en trois étages, et à la 2e édition le dictionnaire entier passe en 18 secondes. La leçon sous le tour de magie : une bonne représentation fait le travail à votre place.

3Le calcul au dos de l'enveloppe

La colonne la plus réutilisable du livre apprend à estimer avant de construire. Les règles tiennent sur une diapo : « deux réponses valent mieux qu'une » (estimer le débit du Mississippi par section × vitesse, puis par bassin versant × pluie ; si elles concordent, on s'y fie), vérifier les dimensions, et garder des règles de pouce sous la main. La perle : « π secondes font un nanosiècle », juste à un demi pour cent près. Déroulons-la sur le calcul d'anagrammes par force brute :

# combien de temps pour 10²¹ opérations à ~1 milliard/seconde ?
10²¹ ops ÷ 10⁹ ops/s        = 10¹² secondes
# règle de pouce : π × 10⁷ secondes ≈ 1 an
10¹² s ÷ (3,15 × 10⁷ s/an)  ≈ 30 000 ans   # verdict connu avant le déjeuner

L'anecdote qui justifie toute la colonne : un directeur technique, en revue d'un système proposé pour les Jeux olympiques, chronomètre sur un coin de nappe l'aller-retour d'un message d'un caractère et conclut que le design ne marche que s'il y a « au moins cent vingt secondes dans chaque minute ». Design refusé ; le système livré un an plus tard a fonctionné sans accroc. L'annexe qui pique : un quiz de dix questions où l'on donne des fourchettes à 90 % de confiance ; la plupart des gens en réussissent 3 à 6 au lieu des 9 attendues. Nous sommes tous trop sûrs de nous, et c'est mesurable.

L'anecdote qui justifie toute la colonne : un directeur technique, en revue d'un système proposé pour les Jeux olympiques, chronomètre sur un coin de nappe l'aller-retour d'un message d'un caractère et conclut que le design ne marche que s'il y a « au moins cent vingt secondes dans chaque minute ». Design refusé ; le système livré un an plus tard a fonctionné sans accroc. L'annexe qui pique : un quiz de dix questions où l'on donne des fourchettes à 90 % de confiance ; la plupart des gens en réussissent 3 à 6 au lieu des 9 attendues. Nous sommes tous trop sûrs de nous, et c'est mesurable.

4Le TRS-80 qui bat l'Alpha

Un seul problème (la sous-séquence contiguë de somme maximale), quatre algorithmes, du cubique au linéaire. Puis le livre organise le combat que personne n'oublie : l'algorithme cubique, en C compilé, sur une station Alpha à 533 MHz, contre l'algorithme linéaire, en BASIC interprété, sur un TRS-80 des années 1970 à 2 MHz. Au-delà de n ≈ 10 000, la pièce de musée gagne. À n = 1 000 000 : 19 ans pour l'Alpha, 5,4 heures pour le TRS-80.

L'épilogue de la 2e édition ajoute un clin d'œil : en relançant les mesures de la 1re édition quatorze ans plus tard, Bentley a trouvé son Pentium II « presque exactement mille fois plus rapide que le vénérable VAX », avec des coefficients algorithmiques quasi identiques. Les machines changent par puissances de dix ; les maths ne bougent pas.

5La recherche binaire est publiée en 1946. Une version juste a pris bien plus longtemps.

La Column 4 ouvre sur une question piège : « la première recherche binaire a été publiée en 1946 ; quand la première recherche correcte l'a-t-elle été ? » L'écart se mesure en années. Le bug le plus célèbre se cache dans une ligne d'apparence anodine :

lo = 0; hi = n - 1;
while (lo <= hi) {
  mid = (lo + hi) / 2;       // ✗ lo + hi DÉBORDE l'entier sur de grands tableaux
  mid = lo + (hi - lo) / 2;  // ✓ même valeur, sans débordement (corrigé en 2006 !)
}

Bentley se sert de cet algorithme « simple » pour enseigner la vérification : écrire d'abord l'invariant de boucle (ce qui doit être vrai à chaque tour, ici « si x existe, il est entre lo et hi »), et dériver le code depuis lui, au lieu de tapoter le code jusqu'à ce que les tests passent.

La Column 5 complète la méthode avec l'échafaudage : un harnais de test jetable autour de la fonction, des assertions qui documentent ce qui doit tenir, du chronométrage automatisé. Le code compagnon livre neuf versions de la recherche binaire, dont une volontairement fausse, pour que le harnais prouve sa valeur. C'est le grand-père du TDD, vingt ans en avance, en C de K&R.

6Déboguer est un exercice d'incrédulité

La section débogage (5.10) est une petite anthologie de bugs impossibles qui avaient tous une explication ennuyeuse. Le programmeur qui peut se connecter assis mais pas debout : deux touches du clavier interverties, et il ne tape pas pareil debout. Le système bancaire de Chicago qui plante quand un client tape « Quito » : le terminal le lit comme une commande quit. Le système qui « a marché une fois, deux fois » : une variable initialisée au chargement et jamais réinitialisée.

L'attitude professionnelle, selon Rick Lemons : la meilleure leçon de débogage de sa vie fut un spectacle de magie. La colombe n'est pas vraiment sortie de nulle part, et votre bug n'est pas vraiment impossible ; dans les deux cas, vous regardiez la mauvaise main. « Déboguer, c'est d'habitude refuser de croire » (Column 5) : refusez l'explication surnaturelle et l'explication logique remonte.

7Chaînes de perles : la Bible, l'Iliade et le grand-père des LLM

La colonne ajoutée en 2000 joue avec du gros texte. Compter les mots de la Bible du roi Jacques (789 616 mots, 29 131 distincts ; « the » apparaît à lui seul 62 053 fois) devient un banc d'essai : une table de hachage maison de 30 lignes bat la map de la STL C++ d'un ordre de grandeur. Un suffix array (trier tous les suffixes du texte ; les voisins partagent leurs préfixes) trouve le plus long passage répété des 807 503 caractères de l'Iliade en 4,8 secondes : une phrase entière que Junon prononce et que Minerve répète mot pour mot.

Puis le clou du spectacle : générer du faux texte en suivant les statistiques de mots d'une source, une chaîne de Markov. Entraîné sur le livre lui-même, l'ordre 2 produit une prose technique troublante de plausibilité, et Bentley note que « pour la parodie, le texte d'ordre 2 est en général le plus savoureux » (Column 15). Prédire le mot suivant à partir des précédents, entraîné sur un corpus : en 2000, c'était un gag de 50 lignes ; multipliez par quelques milliards et vous obtenez les assistants à qui nous parlons toute la journée. La perle est devenue fonds de pension.

8Les règles qui restent

Les deux épilogues sont des interviews fictives où Bentley se cuisine lui-même (« les gens qui s'interviewent eux-mêmes ne devraient pas critiquer les styles d'écriture »). Il en sort, avec les annexes, les règles distillées du livre :

• la checklist de design du premier épilogue : travailler sur le bon problème, regarder les données, sortir l'enveloppe, prototyper, rester simple, viser l'élégance ;
• la loi de Tom Duff, citée comme la meilleure réponse à « bibliothèque ou fait main ? » : « chaque fois que possible, volez le code ». En 2026 ça s'appelle npm install, Composer et Stack Overflow ; le réflexe n'a pas pris une ride, seul son nom a changé ;
• la ligne qui résume le goût du livre entier : « les composants les moins chers, les plus rapides et les plus fiables d'un système informatique sont ceux qui n'existent pas » ;
• 27 règles de tuning de code (annexe 4), avec gains mesurés et avertissement intégré : mesurez d'abord, sur VOTRE machine ; les modèles de coûts montrent un malloc de 12 octets qui en consomme réellement 48.