J’ai décidé d’implémenter ça : https://sciencetonnante.wordpress.com/2015/11/06/la-machine-a-inventer-des-mots-version-ikea/ en javascript (pour un faire un petit générateur de mots dans une page web).
Y a une chose sur laquelle je reviens, et c’est pas la première fois, et ça semble trivial, mais ça change tout.
Dans ce script, en gros, j’ai 80 000 mots et je chercher les occurrences de triplets de lettres là-dedans. Donc en fait, j’ai 3 boucles imbriquées (de A à Z) sur chacun des 80 000 mots.
Question tout con : quel est le plus rapide,
– boucler sur les mots, puis sur les lettres ?
Comme ça :
for (w in words) {
for (i in alphabet) {
for (j in alphabet) {
for (k in alphabet) {
check(ijk, w)
}
}
}
}
– boucler sur les lettres puis les mots ?
Comme ceci :
for (i in alphabet) {
for (j in alphabet) {
for (k in alphabet) {
for (w in words) {
check(ijk, w)
}
}
}
}
Mathématiquement, dans les deux cas, on fait 80 000 × 26³ = 1,4 milliards de boucles.
Pourtant, avec une toute petite astuce, on peut rendre le premier code beaucoup plus rapide.
L’idée est qu’il y a 26 lettres dans l’alphabet. Mais les mots font rarement 26 lettres, et quand ils le font, c’est rarement avec toutes les lettres.
On va donc, à chaque boucle, commencer par vérifier si la lettre sur laquelle on est est contenue dans le mot.
Si il n’y est pas, c’est inutile de faire les deux autre boucles internes : la suite contenant la première lettre n’y sera pas non plus. Dans ce cas, on économise 26² boucles pour ce mot :
for (w in words) {
for (i in alphabet) {
if (check(i, w)) {
for (j in alphabet) {
if (check(ij, w)) {
for (k in alphabet) {
check(ijk, w)
}
}
}
}
}
}
Sachant que les mots font autour de ~8 lettres, ça représente (26-8)×26² = 12 168 boucles par mot !
Du coup, au lieu de 1,4 milliards de boucles, on réduit ça directement à 432 millions.
Ensuite, on économise encore sur le test de la chaîne "ij" (si la seconde lettre "j" ne se trouve pas dans le mot, alors on économise 26 boucles par mot : on passe en dessous des 400 millions.
La différence est grande : on a divisé le temps par 3~4 juste avec ça.
Et ça c’est juste une estimation grossière : en français, les mots — surtout les longs — ont plutôt des lettres en doubles que seulement des lettres différentes.
En pratique, je passe d’un temps d’éxécution de ~2 minutes à seulement 3 secondes… J’ai divisé le temps par 40.
Tout ceci est tout bête, tout con, mais pensez-y : parfois une ligne de code en plus, un simple "if" juste avant une fonction lourde peut tout changer.
Ok, fait un test « if » c’est une condition en plus et donc un calcul en plus. Mais si ça permet d’économiser sur une fonction qui prend 40 fois plus de temps… Alors ça en vaut la même. En l’occurrence, si ma fonction prend vraiment 40 fois plus de temps qu’un "if", alors je serait gagnant dès qu’on mot fait moins de 25 lettres différentes, ce qui est toujours le cas en français.
%%
Autre exemple dans mon code : pour faire le teste de présence d’un triple de lettres consécutifs dans un mot, j’utilisais les regex. C’est lourd et lent.
À la place, j’ai opté pour une fonction avec un simple "str.indexOf()", qui regarde si une souschaîne est contenue dans une chaîne. C’est bien plus rapide qu’un regex. Là, le temps a été divisé par un facteur 100 environ.
Sur une page normale, j’imagine qu’on n’aurait gagné que des micro-secondes. Mais quand on boucle 26³ fois sur chacun de 80 000 mots, le gain de temps est monstre.