Débogage par dichotomie

Je suis peut-être le seul à appeler cela ainsi, mais je vais vous faire part de la méthode que j’utilise généralement pour déboguer un programme.

Recherche dichotomique

Le principe est expliqué sur Wikipédia, mais je vais vous l’expliquer avec un exemple, celui d’un jeu où le joueur choisit au hasard un nombre entier entre 0 et 100, et l’ordinateur doit le trouver avec le minimum d’essais, guidé par le joueur qui lui répond «plus petit», «plus grand» ou «gagné!».

L’algorithme consiste à diviser par deux l’intervalle de recherche à chaque coup. Disons que le joueur a choisi le nombre 13, on aura la séquence:

  • Au départ l’intervalle de recherche est [0; 100], l’ordinateur propose le milieu de cet intervalle, soit 0+(100-0)/2 = 50
  • Le joueur répond «plus petit»
  • L’intervalle est réduit à [0; 50], l’ordinateur propose 0+(50-0)/2 = 25
  • «plus petit»
  • L’intervalle est réduit à [0; 25], l’ordinateur propose 0+(25-0)/2 = 12 (c’est évidemment une division entière).
  • «plus grand»
  • L’intervalle est réduit à [12; 25], l’ordinateur propose 12+(25-12)/2 = 18
  • «plus petit»
  • L’intervalle est réduit à [12; 18], l’ordinateur propose 12+(18-12)/2 = 15
  • «plus petit»
  • L’intervalle est réduit à [12; 15], l’ordinateur propose 12+(15-12)/2 = 13
  • «gagné!»

Débogage

Le travail du code est de prendre des données d’entrée, de leur appliquer un traitement, et d’obtenir des données de sortie. Cela signifie qu’il y a une chaîne de composants (objets, méthodes, fonctions…) qui mènent des entrées vers la sortie.

Vous devez commencer à saisir le parallèle: appliquer l’algorithme de dichotomie signifie identifier la chaîne de composants — l’intervalle de recherche — et inspecter au débogueur les variables. Si c’est correct à un endroit donné, alors le problème se situe en aval dans la chaîne, sinon, en amont.

Par exemple, disons que votre application permette de prendre une photo avec votre smartphone qui sera affichée sur un site web. Or vous prenez une photo et elle n’apparaît pas sur le site. Disons que la chaîne de composants ressemble à ça:

  • sur le smartphone, prendre la photo
  • la redimensionner
  • la convertir en Base64
  • l’envoyer en POST Form au site
  • sur le serveur web, traiter la requête POST
  • reconvertir le base 64 en binaire
  • enregistrer l’image sur disque
  • écrire le chemin du fichier en base de données
  • utiliser l’image lors de la composition de la page web

D’après mon algorithme de débogage, le premier test serait donc d’aller vérifier si on reçoit une requête POST quand l’image est envoyée par le smartphone.

J’ai évidemment simplifié mon exemple, puisque chaque étape ci-dessus est elle-même effectuée par un certain nombres de fonctions ou d’objets. Là encore, j’utilise la dichotomie pour restreindre mes vérifications.

Cette méthode économise des efforts, en évitant d’aller vérifier chaque point de la chaîne.

Finalement, la principale limite de cette technique est qu’il faut connaître suffisamment l’implémentation pour délimiter correctement l’intervalle de recherche.