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.