Accueil › Coding & algorithmique › Invariants, cas limites et tests mentaux
Invariants, cas limites et tests mentaux
Raisonner sur la complexitédebutant
Le code d'entretien échoue rarement sur l'idée. Il échoue sur les bords.
Les cinq cas limites à vérifier systématiquement :
t == null // NPE
t.length == 0 // tableau vide
t.length == 1 // un seul élément
// tous les éléments identiques
// valeurs extrêmes : Integer.MAX_VALUE, nombres négatifs, chaîne vide
L'invariant est l'outil qui rend une boucle juste. Énoncez-le à voix haute avant d'écrire :
// Invariant : à la fin du tour i, max contient le plus grand de t[0..i]
int max = t[0];
for (int i = 1; i < t.length; i++)
if (t[i] > max) max = t[i];
Notez l'initialisation à t[0] et non à 0 : sur un tableau de valeurs négatives, initialiser à 0 renverrait un maximum absent du tableau. Ce genre de détail se décide avant d'écrire la boucle.
Le dépassement d'entier est le piège le plus cité :
int milieu = (bas + haut) / 2; // ✗ peut déborder
int milieu = bas + (haut - bas) / 2; // ✓
Et la technique qui détecte le plus de bugs : dérouler à la main sur trois éléments, en notant les variables à chaque tour.
Les termes à connaître
- Invariant
Une propriété vraie à chaque tour de boucle. « À la fin du tour i,
maxcontient le plus grand des i+1 premiers éléments. » L'énoncer rend le code juste par construction.- Cas limite
Une entrée aux bords du domaine : vide, un seul élément, tous identiques, valeurs extrêmes,
null. C'est là que se cachent presque tous les bugs d'entretien.- Erreur de décalage (*off-by-one*)
Se tromper d'une unité sur une borne :
<au lieu de<=,i + 1au lieu dei. L'erreur la plus fréquente, et la plus facile à détecter en déroulant un petit exemple.- Dépassement d'entier (*overflow*)
intva jusqu'à 2 147 483 647.(a + b) / 2peut déborder sur de grandes valeurs ;a + (b - a) / 2ne déborde pas.- Déroulé à la main
Exécuter son code mentalement sur trois ou quatre éléments, en notant les variables à chaque tour. La technique qui détecte le plus de bugs, avant même de compiler.
- Contrat de la méthode
Ce que la méthode accepte et ce qu'elle garantit. Le fixer avant d'écrire (« entrée nulle : je lève ou je renvoie vide ? ») évite de découvrir le problème en plein exercice.
Cette page présente la partie essentielle de la leçon. Les exemples commentés, les pièges courants et les trois questions de quiz sont dans l'application.