L'intuition géométrique de Hamming
Hamming voyait la géométrie partout
Le chapitre 9 de Hamming s'ouvre avec un avertissement : l'intuition géométrique s'effondre en haute dimension. En 3D, une sphère remplit la majeure partie de son cube englobant. En 10D, la sphère occupe moins de 0,2 % du volume du cube. En 100D, la fraction s'arrondit à zéro. Le volume se concentre près de la surface. Les points se regroupent près des coins, pas au centre.
Ses codes de correction d'erreurs exploitaient cela directement. Les codes de Hamming empilent les mots de code dans un espace binaire n-dimensionnel de sorte que chaque mot de code soit entouré d'une sphère d'erreurs corrigeables. La géométrie détermine le nombre d'erreurs que vous pouvez corriger. L'empilement de sphères en espace n est un problème mathématique aux véritables enjeux : empiler les sphères plus densément, corriger plus d'erreurs.
Le même mode de défaillance géométrique s'applique à la complexité algorithmique. À petit N, O(N²) et O(N) se ressemblent presque sur un graphique. L'écart entre eux semble gérable. À grand N, l'écart explose — exactement comme la fraction de volume de la sphère s'effondre en haute dimension. Ce qui semble traitable à petite échelle devient impossible à l'échelle.
La forme de chaque classe de complexité
Tracer la complexité
Chaque classe de complexité a une forme géométrique :
- O(1) : une ligne horizontale. Même coût indépendamment de N. Pas de pente.
- O(log N) : une courbe légèrement ascendante qui s'aplatit. Double à chaque fois que N est au carré. Croît proportionnellement au nombre de chiffres dans N.
- O(N) : une ligne diagonale passant par l'origine. Le coût croît proportionnellement à N.
- O(N log N) : diagonale légèrement plus raide. Une ligne qui se courbe très doucement vers le haut.
- O(N²) : une parabole. À N=100 : 10 000 opérations. À N=1 000 : 1 000 000 d'opérations.
L'observation critique : le rapport entre deux classes de complexité est lui-même une fonction de N. À N=10, O(N²) coûte 10× plus que O(N). À N=1 000, O(N²) coûte 1 000× plus. À N=1 000 000, ça coûte 1 000 000× plus. L'écart ne croît pas simplement — il croît au taux de N lui-même.
C'est l'argument géométrique pour lequel les patches MOAD-0001 comptent. Déplacer un résolveur de dépendances de O(N²) à O(N) n'est pas une accélération constante. À N=50 000 packages, c'est une accélération de 50 000×. À N=100 000, c'est une accélération de 100 000×. La valeur du patch croît avec la taille du problème.
L'écart qui s'élargit
O(N²) et O(N) produisent tous deux des résultats corrects.
À N=10 : O(N²) coûte 100 opérations, O(N) coûte 10 opérations. Rapport : 10×.
À N=1 000 : O(N²) coûte 1 000 000 opérations, O(N) coûte 1 000 opérations.
Les graphes comme géométrie
Le graphe acyclique orienté
Un DAG (graphe acyclique orienté) est une structure géométrique : des nœuds connectés par des arêtes orientées sans cycles. Les graphes de dépendances de logiciels, les pipelines de construction et les architectures de flux de données forment tous des DAG.
Chaque nœud possède des propriétés géométriques mesurées en comptant ses arêtes :
- Degré entrant : nombre d'arêtes arrivant au nœud. Un degré entrant élevé signifie que de nombreuses dépendances en amont alimentent ce nœud.
- Degré sortant : nombre d'arêtes quittant le nœud. Un degré sortant élevé signifie que de nombreux consommateurs en aval dépendent de ce nœud.
- Centralité d'intermédiateté : degré entrant + degré sortant. Mesure le nombre de chemins qui passent par ce nœud. Un nœud avec une centralité d'intermédiateté élevée se situe à un carrefour du graphe.
- Score de surcharge : accélération × degré entrant. Mesure la quantité de travail qui s'écoule en aval lorsque ce goulot d'étranglement se dégage.
Le modèle usine donne une signification physique à ces propriétés géométriques :
- Centralité d'intermédiateté élevée + score de surcharge élevé = nœud bourreau de travail. Retirer ce goulot d'étranglement sans préparation en aval = effondrement.
- Degré sortant élevé + score de surcharge faible = nœud glouton. Consomme sans produire. La machine qui oublie de s'arrêter.
Surcharge & centralité d'intermédiateté en pratique
Lire un DAG
Considérez une chaîne de 5 nœuds : A → B → C → D → E, plus une arête supplémentaire B → D.
- A : degré entrant 0, degré sortant 1, centralité d'intermédiateté 1. Nœud source. Rien ne l'alimente. Un consommateur.
- B : degré entrant 1 (de A), degré sortant 2 (vers C et vers D), centralité d'intermédiateté 3. Alimente deux nœuds en aval — un point de divergence.
- C : degré entrant 1 (de B), degré sortant 1 (vers D), centralité d'intermédiateté 2. Un nœud de passage.
- D : degré entrant 2 (de B et de C), degré sortant 1 (vers E), centralité d'intermédiateté 3. Reçoit de deux chemins.
- E : degré entrant 1 (de D), degré sortant 0, centralité d'intermédiateté 1. Nœud puits.
B et D partagent la plus haute centralité d'intermédiateté (3). B est le point de divergence : il alimente deux nœuds. D est le point de convergence : il reçoit de deux chemins. Après un patch MOAD-0001 en C, D reçoit une surcharge des deux chemins B→D et C→D simultanément.
Calculer les métriques des nœuds
Un graphe de dépendances : A → B → C → D → E (une chaîne), plus une arête supplémentaire B → D.
Le nœud C a une accélération mesurée de 50× après un patch MOAD-0001.
Le défaut Flatland
MOAD-0007 : Données spatiales interrogées comme une liste plate
MOAD-0007 (le défaut Flatland) : les données spatiales interrogées comme une liste plate ignorent la structure géométrique des données. Chaque requête vérifie tous les N objets. O(N) par requête. Avec M requêtes : O(M × N). À l'échelle : catastrophique.
Un lancer de rayons en temps réel vérifie chaque objet d'une scène contre chaque rayon. À 60 images par seconde, avec 100 rayons par image et 10 000 objets de scène : 60 000 000 tests d'intersection par seconde. Tous évitables.
L'insight géométrique : l'espace a une structure. Les objets se regroupent. Un rayon qui manque la moitié gauche de la scène manque chaque objet de la moitié gauche. Une liste plate ne peut pas exploiter cela — elle vérifie chaque objet indépendamment de l'emplacement spatial. Une structure de données spatiale peut.
Le BVH : Recherche binaire en 3D
Comment fonctionne un BVH
Un BVH (hiérarchie de volume englobant) décompose l'espace 3D en un arbre de volumes englobants imbriqués. Chaque nœud interne contient un volume englobant qui contient toute la géométrie de ses enfants.
Une requête de lancer de rayons :
1. Testez le volume englobant racine. Si le rayon le manque, quittez immédiatement — toute la scène est élaguée.
2. Si le rayon le touche, récursez dans les enfants. Testez le volume englobant de chaque enfant.
3. Pour chaque enfant qui manque : élaguez ce sous-arbre. Pour chaque enfant qui est touché : récursez plus profondément.
4. Aux nœuds feuilles : testez la géométrie réelle.
Géométrie de l'élagage : à chaque niveau, les branches non intersectantes sont éliminées. Avec un BVH équilibré de profondeur d : 2^d nœuds feuilles existent, mais un seul rayon a besoin d'au maximum O(log N) comparaisons pour le chemin élagué.
C'est le même argument géométrique que la recherche binaire : chaque comparaison divise par deux l'espace de recherche restant. La recherche binaire divise par deux un tableau trié. Un BVH divise par deux l'espace 3D visible. La structure est identique — un arbre binaire équilibré avec élagage à chaque nœud.
Un correctif MOAD-0007 : remplacez la liste plate par un BVH. Passez de O(N) par requête à O(log N) par requête. À N=1 024 objets, O(log₂ 1 024) = 10 comparaisons au lieu de 1 024.
Calculer l'accélération du BVH
Une scène de jeu a 1 024 objets.
Sans BVH : un lancer de rayons vérifie les 1 024 objets.
Avec un BVH équilibré de profondeur 10 (2^10 = 1 024 feuilles) : un lancer de rayons traverse au maximum 10 niveaux, avec 2 comparaisons d'enfants par niveau.