Publié par

Il y a 7 ans -

Temps de lecture 4 minutes

Software Craftsmanship 2012 – Génération de séquences de De Bruijn


Première session de cette édition 2012 du Software Craftsmanship de Londres, je me dévoue pour la génération des séquences de De Bruijn dont le nom seul suffit à faire fuir les plus valeureux développeurs. En réalité, j’y vais sans trop savoir ce qui m’attend, si ce n’est que ça va être plutôt scientifique.
Je ne suis pas déçu, une courte présentation nous donne un aperçu des fameuses séquences de De Bruijn et d’une méthode de résolution originale. Celle-ci est basée sur la génération de toutes les possibilités suivie d’une réduction de graphe.

Définition et énoncé de l’exercice

Les mots de De Bruijn sont les chaînes circulaires, les plus courtes possibles, contenant tous les mots de longueur n d’un alphabet A de p lettres.
B(n, p) désigne le nombre de ces mots circulaires de De Bruijn.

Voici l’énoncé de l’exercice:
To generate a B(k,n) de Bruijn sequences one can execute the following algorithm.

  • Generate all combinations of length n−1
  • Connect a combinations w with w|l for each letter l
  • Find an Eulerian Cycle
  • Read off the edge labels

With k= 2, n= 3 and alphabet A= {a, b}.

Résolution de l’algorithme

Ça fume un peu, tout le monde s’acharne à comprendre le fonctionnement de ces fameuses séquences. D’abord sur papier, chacun dessine les graphes, recherche les cycles, puis c’est le moment de se lancer. Daan van Berkel, le speaker hollandais du slot, nous a préparé des environnements dans lesquels les tests sont déjà écrits et le code partiellement. Nous devons remplir les traitements principaux de l’algorithme et faire passer les tests.


Finalement, c’est là que cela se complique fortement. Plutôt que de se lancer dans un exercice, plutôt courant, de TDD, je passe un temps fou à comprendre les tests d’une part et surtout toute l’API qui est utilisée pour faire les traitements et donc valider l’algorithme que je dois écrire. Le code, non documenté, est extrêmement complexe par rapport à l’objectif de l’exercice.

Je me rends vite compte que ma maîtrise fonctionnelle et la complexité de l’API permettent difficilement de résoudre le problème globalement. Je me perdrais à essayer d’aborder le sujet dans sa globalité. 
Je décide de réduire la voilure des tests et de m’attacher aux tests les plus simples puis d’ajouter progressivement de la complexité comme je le ferai en TDD classique. Sauvé, tout s’éclaire, la récursivité ressort clairement après 3 tests ainsi que les conditions d’arrêt. La première classe de tests passe au vert. Ouf.
J’allège le code par quelques cycles de refactoring, c’est bon, je passe à la suite.

Stop!!!!

Pause obligatoire. Les participants sont sommés de sortir de la pièce pour se reposer un peu les méninges. Pas de refus, mais ça va être difficile de terminer.

Reprise: recherche de cycles, c’est reparti avec la même technique :

  1. Décryptage de l’API fournie pour les cycles et du code déjà présent.
  2. Je pars de la base, des concepts les plus simples, et j’avance dans la complexité par itération.
  3. Refactoring.

La deuxième partie se passe sans trop d’encombre, j’avance tranquillement. Mon voisin essaye d’installer Git sur son PC… La journée s’annonce longue pour lui…

Conclusion ?

J’approche de la fin, la cloche sonne, Daan nous interrompt, et demande s’il y a des questions. La première remarque concerne le code existant qui nous a fait perdre beaucoup de temps, il l’admet. Et puis rien. Juste au revoir.
Je viens de passer 2h sur un algorithme juste comme ça, sans objectif particulier. C’est plutôt frustrant, j’espérais découvrir quelque chose de nouveau, une technique, une façon différente d’appréhender les choses, d’aborder ce type de développement. Et bien non, je suis juste venu à Londres faire un exercice d’algorithmique. Évidemment, c’est toujours intéressant de pratiquer et il en ressort toujours quelque chose, mais c’est tout de même frustrant.

Que retenir donc de cette session?

  • Un nouvel exercice pour changer des suites de fibonacci.
  • KISS: l’API était vraiment surdimensionnée par rapport à l’objectif de l’exercice. Résultat: une moins grande efficacité pour un même résultat.
  • Emergent design: l’algorithme complet n’étant pas immédiat, l’aspect itératif du TDD m’a permis de faire ressortir rapidement et simplement les différentes briques de l’algorithme sans pour autant l’avoir conceptualisé auparavant.

Publié par

Commentaire

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Nous recrutons

Être un Xebian, c'est faire partie d'un groupe de passionnés ; C'est l'opportunité de travailler et de partager avec des pairs parmi les plus talentueux.