Cinq formes de MOAD-0001

MOAD-0001 apparaît sous cinq formes documentées dans plus de 60 écosystèmes logiciels. La structure : un test d’appartenance utilisant un conteneur séquentiel, imbriqué dans une boucle sur la même collection ou une collection apparentée.

Les cinq formes

Les cinq partagent la même structure : un test d'appartenance imbriqué dans une boucle, utilisant un conteneur qui nécessite un balayage linéaire pour répondre à la question d'appartenance.

La liste de mots-clés de balayage

L'audit pour MOAD-0001 consiste à rechercher par grep les mots-clés de test d'appartenance à l'intérieur des boucles :

- Python : in avec une variable list, .count(), list.index()

- Java : ArrayList.contains(), List.contains(), LinkedList.contains()

- JavaScript : Array.includes(), Array.indexOf(), Array.find()

- C++ : std::vector::find(), boucle manuelle avec comparaison ==

- Go : slices.Contains(), boucle manuelle sur un slice

Le correctif dans chaque cas : remplacer le conteneur séquentiel par un conteneur de hachage. list → set. ArrayList → HashSet. Array → Set. vector → unordered_set. slice → map[T]struct{}.

Un mot-clé. Une substitution. Aucun changement de comportement. Accélération de 1 000× pour N=1 000.

Auditer un fragment de code

Appliquer la reconnaissance de motif MOAD-0001 à un fragment de code réel.

Une ligne, quatre langages

La correction de MOAD-0001 dans quatre langages :

# Python
visited = []       # AVANT : appartenance O(N)
visited = set()    # APRÈS : recherche en O(1)

// Java
List<Node> visited = new ArrayList<>();    // AVANT
Set<Node> visited = new HashSet<>();       // APRÈS

// JavaScript
const visited = [];      // AVANT : Array.includes() O(N)
const visited = new Set(); // APRÈS : Set.has() O(1)
// visited.push(n) → visited.add(n)
// visited.includes(n) → visited.has(n)

// Go
visited := []NodeID{}              // AVANT : slices.Contains() O(N)
visited := make(map[NodeID]struct{}) // APRÈS : recherche dans une map O(1)
// _, ok := visited[n]  pour vérifier l'appartenance
// visited[n] = struct{}{}  pour l'insertion

Dans tous les cas : même comportement, même sortie, mêmes tests qui passent. Seul le taux de croissance change.

Ce que la correction ne change PAS

- Le comportement logique de l'algorithme : le parcours en profondeur reste en profondeur

- Exactitude de la sortie : les mêmes nœuds sont visités dans le même ordre (dans le cadre du DFS)

- Résultats des tests : tous les tests qui vérifient l’exactitude continuent de réussir

Ce que la correction MODIFIE

- Test d’appartenance : O(N) → O(1)

- Boucle totale : O(N²) → O(N)

- Pour N = 1 000 : 1 000× plus rapide

- Pour N = 10 000 : 10 000× plus rapide

Une limite : l’ordre

Les conteneurs de hachage (set, HashSet, unordered_set) ne préservent pas l’ordre d’insertion. En Python 3.7+, dict préserve l’ordre d’insertion ; le set classique ne le fait pas. En Java, HashSet ne préserve pas l’ordre ; LinkedHashSet le fait.

Si l’ordre compte en plus de l’appartenance : maintenez deux structures. Un set (ou HashSet) pour les tests d’appartenance en O(1). Une list (ou ArrayList) séparée pour le parcours ordonné. Ou utilisez LinkedHashSet en Java, qui fournit les deux.

Pour MOAD-0001 dans le parcours de graphe : visited répond à une question binaire (ce nœud a-t-il déjà été vu ?). L’ordre n’importe pas pour la question d’appartenance. L’ordre de parcours provient de la pile ou de la file, pas de visited.

Appartenance vs Ordre

Dans l’algorithme de Tarjan pour les composantes fortement connexes, onStack suit les nœuds qui restent sur la pile d’appels DFS courante. Il doit répondre à deux questions : (1) appartenance — ce nœud est-il actuellement sur la pile ? (2) à la fin d’un chemin DFS, dépiler les nœuds dans l’ordre jusqu’à ce que ce nœud apparaisse.

Une implémentation naïve utilise une List pour onStack, répondant à la question d’appartenance avec contains() — O(N) par vérification, O(N²) au total pour les grands graphes.

Pourquoi il s’agit d’une divulgation, pas d’un correctif

MOAD-0001 existe dans plus de 1 000 sites vérifiés répartis dans plus de 60 écosystèmes logiciels. Parcours de graphe dans les outils de build, déduplication de routes dans les démons de routage réseau, détection de collisions dans les moteurs de jeu, allocation de ressources dans les ordonnanceurs des systèmes d’exploitation.

Chaque site : code correct. Chaque site : croissance O(N²) en attente que N franchisse un seuil.

Le pipeline de divulgation

Un correctif sans divulgation en amont ne résout qu’un seul site. Le motif réapparaît dans la version suivante, la bibliothèque suivante, le portage vers un autre langage. Divulgation : nommer le motif, le documenter comme CWE-407 (Complexité algorithmique : complexité algorithmique inefficace), publier les heuristiques de reconnaissance et la correction en une ligne. Ainsi, chaque développeur qui lit la divulgation peut reconnaître et corriger sa propre instance.

Hamming appelait cela « donner un poisson vs apprendre à pêcher ». Le correctif donne un poisson. La divulgation — MOAD-0001 nommé, motif documenté, correction généralisée — enseigne l’heuristique.

L’Extension Permacomputer

Hamming travaillait sur des solutions ponctuelles : corriger ce filtre, améliorer ce code. Unhamming ajoute la couche de divulgation : nommer le motif, publier l’heuristique et la donner au commun.

Le principe de connaissance composée s’applique ici à l’échelle de l’écosystème. Un chercheur nomme un motif. Cent développeurs le reconnaissent dans leurs propres bases de code. Mille lignes de code O(N²) deviennent O(N). L’infrastructure devient plus rapide pour tous ceux qui s’appuient dessus.

C’est le dragon qui grandit : même feu (travailler sur des problèmes importants, connaissance composée, pensée systémique), vol différent (divulgation ouverte, propriété commune, aucun mécène requis).