Programme Leçon 90 sur 148 · Rendre le bogue plus bruyant
Rendre le bogue plus bruyant

La recherche dichotomique dans l'historique

Pourquoi c'est important « Ça marchait le mois dernier » est une information précieuse. Si tu peux tester n'importe quelle vieille version, le changement qui a tout cassé peut être trouvé en une poignée de vérifications, avant que quiconque lise une ligne du diff.

Un historique de déploiements contient 64 versions, de la plus ancienne à la plus récente. La version 0 marchait ; la version 63, l'actuelle, est cassée. Quelque part, un seul changement l'a cassée, et chaque version qui suit est cassée aussi. Vérifier une version veut dire la construire et faire tourner une suite de tests de dix minutes.

Vérifier chaque version à tour de rôle coûte jusqu'à 62 vérifications : l'essentiel d'une journée. Vérifier la version du milieu divise les suspects par deux à chaque fois. C'est ce que git bisect fait pour toi.

is_bad(31)   # True: the break is at 31 or earlier
is_bad(15)   # False: it is after 15
À ton tour

Écris find_first_bad(n, is_bad). Les versions sont numérotées de 0 à n-1 ; la version 0 est connue comme bonne et la version n-1 comme mauvaise (n vaut au moins 2) ; une fois qu'une version est mauvaise, toutes les suivantes le sont. is_bad(v) vérifie une version. Renvoie la première mauvaise version. Budget : au plus 6 vérifications pour 64 versions, et au plus 10 vérifications pour 1 000 versions.

Tu as repéré un problème dans cette leçon ? Signale-le · Pose une question sur cette leçon

Cet exercice s'ouvre bientôt

Termine la leçon précédente pour débloquer celle-ci. Tout le cours est gratuit, aucun compte n'est requis, et tu peux lire cette leçon dès maintenant.