La Grille
L'origine de « La Grille » est un atelier du « Games Creators Network » où il s'agissait de créer un programme de génération de grilles de mots de type mots croisés.
Un programme de génération simple peut être développé en quelques heures, et il donnera de bons résultats. J'ai cependant pris le parti de développer ma contribution de manière un peu plus longue mais avec plusieurs objectifs :
- une structure permettant d'essayer plusieurs stratégies simplement ;
- un programme testé ;
- un programme au moins aussi rapide que les contributions faites rapidement.
Pour plus de renseignements sur les objectifs, allez voir les objectifs initiaux.
Le programme est en C++.
Le site « La Grille »
Au fur et à mesure du développement du programme, je me suis servi de celui-ci comme d'atelier personnel pour tester des outils de profiling, de compilation, des idées d'architecture. L'idée m'est alors venue de partager cet atelier sur un site web.
Le programme, en cette ouverture de site, peut déjà construire des grilles, sans cases noires. Il est gourmand en mémoire et en temps machine, ses grilles sont assez monotones, il n'exploite qu'un seul processeur,… bref, il est loin d'être un bon générateur de grille.
Cependant, ses fondations lui permettent, j'en suis certain, d'être amélioré par étapes simples et explicables, ce que je vais tenter de faire ici.
Les pages du site peuvent être commentés pourvu que vous y soyez enregistré.
Le programme
Pour suivre le déroulement du développement, il vous faudra lire les fichiers sources du programme.
Pour cela, dirigez-vous vers obtenir le programme.
Puis il vous faudra compiler le programme si vous voulez le lancer (ce n'est pas obligatoire si vous ne voulez que suivre les modifications).
Les articles
Le danger de l'instinct
Lorsque l'on programme, on développe des instincts : des habitudes ou des préjugés venus d'expériences que l'on fait, de ce qu'on lit, de ce que l'on comprends ou croit comprendre.
Il faut se méfier de cet instinct.
Voici un exemple avec DictionarySimpleImpl. L'implémentation initiale, on l'a vu, est un simple std::vector dans lequel on cherche intégralement à chaque demande de mot.
Ce que l'on veut, dans un dictionnaire, c'est une recherche rapide, peu importe le temps d'insertion. L'idée qui vient est alors : pourquoi pas un std::set ?
L'implémentation est en plus extrêmement simple : voir le code.
Et voici un graphique de performances :
En vertical, le temps pris pour la résolution de la grille avec la version actuelle. En bleu, version std::vector, en rouge, version std::set. Dans le domaine de résolution actuel, la version std::vector est… plus rapide (sauf pour la dernière résolution, qui est une grille 5×4).
Est-ce pour autant une mauvaise optimisation ? Rien ne nous le dit. Sur la dernière valeur, std::set est légèrement plus rapide. Il se trouve qu'au delà, à 5×5, la version actuelle de La Grille n'est pas capable de trouver une solution dans un temps acceptable.
Peut-être que lorsque La Grille sera capable de résoudre des grilles de 5×5 et plus, la version std::set sera plus intéressante.
Moralité : se méfier de l'instinct. Se reposer sur des outils de mesure.
Un profiler, par exemple.
Restriction du dictionnaire
À l'épisode précédent, je terminais en disant que le code de la restriction du dictionnaire n'était pas encore disponible. Il l'est à présent sur GitHub à la révision 20d8c96…
Dans cet épisode, je vais montrer comment j'ai ajouté la fonctionnalité de filtre au dictionnaire et expliquer les choix.
Quelques mesures pour démarrer
Dans un premier temps, comme je le disais, et avant de gérer les cases noires, je vais faire une passe d'optimisations. En l'état, le programme s'affole très vite, les temps de calculs deviennent trop grand pour que le programme soit utilisable.
J'ai commencé par faire des mesures sur des tailles de grilles croissantes. Les temps réels mesurés n'ont que peu d'importance, ce qu'il faut voir, c'est la rapidité avec laquelle les courbes s'élancent vers l'infini.
État des lieux initial
Dans ce premier article, faisons un peu le tour de « La Grille » à la révision 1.
En ligne, vous pouvez consulter les sources sur GitHub.
Si vous avez cloné le dépôt en local, synchronisez vous sur cette révision : git reset 903668e
