POC d’un système de réservation pour un concert

L’application des consignes sanitaires…peut être très contraignante :

D’où l’idée de mettre en œuvre une réservation préalable.

Mais comment recueillir des intentions de présence fiables pour un concert gratuit ?

La solution retenue a été de transmettre un code de réservation par SMS.

Et de contrôler les entrées (et la limite de remplissage) avec les codes présentés par les personnes à l’entrée.

Bilan

44  des 48 places possibles ont été réservées en 4 jours seulement. Ensuite le site présentant le concert a affiché « Complet ! ». Les 4 places restantes ont été mises de coté et utilisées pour accueillir des spectateurs n’ayant pas réservé de place.

Parmi les 22 numéros de téléphone portable saisis pour ces réservations, 4 étaient erronés et n’ont donc pas reçu de code par SMS.

Sur les 18 codes de SMS envoyés, 3 n’ont pas été confirmés ; au moins pour d’entre-eux, il s’agissait manifestement d’une erreur de saisie de numéro puisque une demande de réservation a été confirmée ensuite avec un numéro presque identique (1 seul chiffre différent).

Il était possible de réserver 1 à 4 places par numéro de téléphone portable. Un groupe de 12 personnes a utilisé 3 portables pour réserver ses places.

Personne ne s’est présenté avec un code non confirmé.

Il aura malheureusement fallu refuser du monde pour ce concert mais l’idée de recueillir un engagement pour une entrée gratuite en demandant un numéro de téléphone portable a donc été validée par cette expérience.

Et, par ailleurs, le concert a eu beaucoup de succès !

Et en C++ ?

La comparaison entre VBA, Phyton, PHP ou C restait dans un style procédural. Et si on s’aventurait dans l’orienté objet ?

Allez changeons de paradigme, attention c’est bestial :
Zouen Orienté Objet !

On pourrait transcrire le code en C quasi directement en C++. Après tout, les méthodes des objets sont écrites dans un langage procédural. Mais ce serait sans intérêt et contraire à la philosophie de l’orienté objet. En OO, l’approche quitte nécessairement le procédural pour aller dans le conceptuel…

Comment un développeur OO voit une grille de sudoku ? Comme ça :

C’est à dire sous la forme de 9 régions, elle-même composées de 9 valeurs ; un embryon de structure fractale. On définit alors deux classes :

  • une classe pour les régions,
  • une classe pour la grille d’un sudoku.

La classe Region


Une instance de la classe Region contient quelques attributs privés :

  • une grille de 3×3 valeurs comprises entre 0 et 9
  • une position d’une case courante dont les coordonnées en ligne, colonne sont mémorisées par deux entiers l et c.

Et quelques méthodes triviales (c’est  à dire dont les noms devrait suffire à évoquer leurs fonctions), à quelques exceptions près :

  • suivante() passe la case courante à la position suivante et retourne un booléen « vrai » si on atteint la dernière case ou « faux » sinon,
  • teste(v) vérifie si la valeur v est adaptée à la position courante,
  • ajoute(v) affecte la valeur v à la position courante et passe celle-ci à la case suivante,
  • dup() crée une copie d’une instance,
  • val(l,c) retourne la valeur de la grille privée en ligne l et colonne c (indépendamment de la case courante).

La classe Grille


La classe Grille est à peine plus complexe.

Son constructeur commence par dresser la liste de toutes les régions possibles :

______#0

 

______#1
1 2 3
4 5 6
7 8 9
______#2
1 2 3
4 5 6
7 9 8
______#3
1 2 3
4 5 6
8 7 9

 

...

 

______#362879
9 8 7
6 5 4
3 1 2
______#362880
9 8 7
6 5 4
3 2 1

Il n’y en a que 9! (plus une pour la région vide, une quantité négligeable pour le développeur OO) dont le nombre est mémorisé dans l’attribut publique nbRegions et chaque cas possible dans le tableau Regions de pointeurs sur des instances de la classe Region. C’est la méthode privée listeRegions() qui est chargée de renseigner la liste des régions possibles.

Par ailleurs, la classe Grille contient quelques attributs et méthodes privés :

  • un tableau de 3×3 régions choisies chacune parmi les 362 881 régions possibles,
  • une grille de 9×9 valeurs comprises entre 0 et 9 qui correspondent au choix des 9 régions, mise à jour grâce à la méthode privée enGrille(),
  • les contraintes à respecter pour le sudoku recherché,
  • une position d’une case courante dont les coordonnées en ligne, colonne sont mémorisées par deux entiers l et c.

Les méthodes publiques de la classe Grille font ce que leur nom exprime, valide(r) étant l’équivalent de teste(v) de la classe Region.

La beauté d’un code OO

Une fois ce travail préliminaire effectué, la recherche d’une solution pour un sudoku est spectaculairement concise et lisible :

C’est si beau qu’on en pleurerait d’émotion.

Les horreurs cachées

L’envers du décor l’est beaucoup moins.

Un travail considérable

Même en se contentant de l’encapsulation de l’approche OO (on laisse de coté les notions d’héritage et de polymorphisme), les 113 lignes de code de la solution en C sont remplacées par 365 lignes réparties en 5 fichiers (region.h, region.cpp, grille.h, grille.cpp et sudoku.cpp).

Un résultat lamentable

Les toutes dernières version de Python, PHP et C++ n’étant pas disponibles sur le serveur utilisé pour les tests de performance de l’article précédent, on les refait sur un serveur fraichement installé (Centos 8 en l’occurrence) :

  • 3 s en Python3,
  • 1 s en PHP 7,
  • 0,04 s en C,
  • 45 s en C++ !

A propos, la première solution trouvée en C++ est différente de celles trouvées dans les autres langages :

 2 1 4 3 6 5 8 9 7
 3 5 6 7 8 9 1 4 2
 7 8 9 1 4 2 3 5 6
 4 9 5 2 1 7 6 3 8
 8 2 7 9 3 6 4 1 5
 1 6 3 8 5 4 7 2 9
 6 7 2 4 9 1 5 8 3
 5 3 1 6 2 8 9 7 4
 9 4 8 5 7 3 2 6 1

Voilà un très bel exemple pour la loi de Less 🙂

Conclusion

Il ne faudrait surtout pas jeter le bébé avec l’eau du bain : en déduire que l’approche orienté objet serait inefficace serait une grave erreur !

Car ici, dans le cas particulier de la résolution d’un sudoku, elle est inadaptée. C’est un problème trop simple.

Pour d’autres situations plus complexes, l’approche orienté objet apporte bien au contraire une vision salvatrice, comme suggéré par la simplicité du code principal de résolution d’un sudoku en C++.

Sans oublier que les programmes conçus pour ces tests sont certainement perfectibles.

(Sources des exemples de code sur demande)

VBA, Python, PHP ou C : c’est pareil ?

Prenons un exemple quasi idéal pour un traitement informatique : le sudoku.

La première préoccupation de l’informaticien est de choisir une représentation des données et de préciser les interactions avec l’utilisateur.  Le sudoku étant une grille de nombres, on saute sur la facilité en choisissant d’emblée le contexte d’un tableur.

En VBA

Pour repérer les contraintes initiales on les met tout simplement en gras ; par exemple :

Voici alors une solution en VBA de ce problème :

Non seulement c’est illisible mais en plus c’est lent mais alors lent de chez lent.fr !

7 minutes (et 32 secondes) ! Il faut être patient et avoir confiance en la validité du code car Excel devient comateux pendant la durée du traitement.

Mais bon, ça fait le boulot ; voici la première solution trouvée :

Il faut avouer que les contraintes de ce sudoku ont été vicieusement choisies pour nécessiter un grand nombre d’itérations.

En Python

Considérons une version de ce traitement plus pédagogique, écrite cette fois en Python :

Et la même solution est obtenue en seulement 2.2 secondes :

 2 1 4 3 6 5 8 9 7
 3 5 6 7 8 9 1 2 4
 7 8 9 2 1 4 3 5 6
 4 9 5 1 3 7 2 6 8
 8 2 7 9 4 6 5 1 3
 1 6 3 8 5 2 7 4 9
 5 7 1 4 9 3 6 8 2
 6 4 2 5 7 8 9 3 1
 9 3 8 6 2 1 4 7 5
Trouvé en 1453557 itérations.

Le Python a en plus l’avantage d’imposer la présentation du code, ce qui en rend la (re)lecture plus accessible à tous (même à son auteur lorsqu’il doit y revenir plusieurs années après).

En PHP

Pour le fun, le même traitement mais en PHP :

Malgré une petite optimisation du traitement qu’un regard attentif aura repéré aux lignes 23-26, c’est un tout petit peu plus lent : 2.7 secondes.

C’est d’ailleurs cette proximité de temps de traitement qui aura motivé la recherche (empirique) de contraintes nécessitant un grand nombre d’étapes (itérations) pour obtenir une première solution, pas moins de 1 453 557 étapes de traitement pour trouver une première solution qui satisfait les contraintes choisies pour l’exemple.

En C

Mais alors en C, cela donne quoi ?

0,08 secondes.

Si, c’est bien 8 centièmes de secondes… c’est à dire plus de 5600 fois plus rapide qu’en VBA et 200 fois plus rapide qu’en Python !

En prime le code est bien plus beau :

Une démarche commune

Ces quatre exemples ont en commun un style de programmation procédural (à opposer par exemple à une approche orientée objet) et la démarche du traitement.

La grille du sudoku est gérée informatiquement dans un tableau dont chaque case, repérée par ses indices de ligne (l) et de colonne (c) contient la valeur numérique (v) du chiffre qu’elle contient. Un 0 code pour une case vide.

Le traitement est réparti en deux fonctions :

  • valide(v,l,c)
  • cherche(v,l,c)

La première fonction vérifie la validité d’une valeur v mise dans la case (l,c). On y vérifie que la valeur v n’est pas déjà présente sur la ligne l, ni sur la colonne c ni dans la région de 3×3 cases à laquelle la case (l,c) appartient.

La deuxième fonction est récursive (elle s’appelle elle-même). Elle cherche d’abord quelle valeur serait valide dans la case en cours et elle s’assure ensuite que cette valeur est compatible avec une solution pour le reste de la grille, à commencer par la case suivante. Si cette deuxième condition n’est pas vérifiée, on essaye une autre valeur. Si on a épuisé toutes les valeurs possibles, on remet en cause la valeur choisie à la case précédente.

Et si on arrive à trouver une valeur valide pour la dernière case de la grille, on a trouvé une solution !

Des différences de « détails »

Mais écrire ce même traitement en VBA, Pyhton, PHP ou C n’est pas du tout la même histoire.

La solution en VBA comparée à celles en Python, PHP ou C se singularise par sa dépendance au contexte d’Excel. La différence saute aux yeux.

Les solutions en Python, PHP ou C se ressemblent beaucoup plus. Elles comportent néanmoins des subtilités qui pourraient faire perdre un temps fou à l’expert d’un de ces langages qui voudrait en utiliser un autre dont il est moins familier.

Quelques exemples :

La structuration du code

Les blocs d’instruction en Python sont définis par l’indentation (le décalage par rapport à la marge de gauche) et par des accolades en PHP  ou en C. Cette contrainte de présentation du Python que l’on avait aussi en Fortran est une gène pour le programmeur expérimenté et isolé mais une aide pour le débutant ou les équipes de programmeurs.

La gestion des variables

En C, il faut déclarer préalablement chaque variable et préciser le type de données pour lequel elle sont prévues. Il faut  même réserver (et ensuite libérer) explicitement de l’espace en mémoire dans certains cas (non illustré dans l’exemple).

En PHP, les variables sont identifiées par un $ et gérées automatiquement. On peut même utiliser la même variable pour y stocker des types de données différentes. Par rapport au C, c’est cool mais on se retrouve avec des $ partout.

En Python, les variables sont identifiées et gérées automatiquement.

Il y a aussi des différences sur la visibilités des variables. En C, les variables globales sont visibles partout ; une joyeuse source d’erreur. En Python ou PHP, il faut les introduire dans les fonctions avec le mot clé « global ».

Cette évolution de la gestion des variables va dans le sens de la simplicité pour le programmeur. Un des prix à payer est une concession sur les performances.

Les aspects plus techniques

La différence entre le Python, le PHP ou le C est encore plus grande pour des aspects plus prosaïques mais néanmoins incontournables.

Les exemples donnés en illustration les masquent pudiquement. Il s’agit notamment des instructions qui affichent la solution trouvée ou, plus encore, qui initialisent la grille du sudoku et ses contraintes. La maîtrise de ces aspects plus techniques fait toute la différence entre un développeur débutant ou expérimenté ; et cela n’a rien à voir avec une question de syntaxe !

Il y a aussi une autre nuance importante qui distingue le Python ou le PHP avec le C. Les deux premiers langages sont interprétés, le C est compilé. Cette étape de compilation assure un gain de performance considérable à l’exécution mais entraîne une complexité et une charge supplémentaire pour le programmeur.

L’art de l’informaticien

Ce n’est pas la maîtrise d’un langage qui fait l’informaticien, pas plus que l’usage d’une souris ou d’un clavier ni la connaissance d’un « framework » ou d’un IDE.

Au final, l’ordinateur exécutera systématiquement et à un vitesse sur-humaine des instructions élémentaires (chaque instruction réalisant une action ridiculement simple).

L’art de l’informaticien s’exprime dans la conception d’une démarche de traitement bien adapté pour résoudre un problème donné.

Et c’est universel.

(Sources des exemples de code sur demande)