#17705

Note : optimiser les boucles en programmation

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.

https://lehollandaisvolant.net/?mode=links&id=20180822215950

#17704

Women's Pockets are Inferior.

Sur les pantalons, les poches sont environ moitié moins grande sur tailles "femme" que sur les tailles "homme". D’après cet article, on peut tout juste y mettre un smartphone 5", et pas ses mains.

Non seulement c’est ridicule, mais surtout… pourquoi ?

D’après l’article (à la fin), ça serait une question de mode… wtf

https://pudding.cool/2018/08/pockets/

#17703

space: The Next Trillion Dollar Industry - YouTube

De nouveau, un exemple pourquoi "permettre l'accès à l'espace aux entreprises privées" :

- N'EST PAS synonyme de "je laisse tel ou tel milliardaire tuer des éléphants sur Mars durant son temps libre"
- N'EST PAS nouveau : ça fait des décennies que des entreprises privées possèdent des satellites en orbite, ne serait-ce que pour faire les cartes routière, diffuser des émissions de TV, permettre des télécommunications satellites (pour info : Google Maps utilise des photos prises par des satellite privés, et OSM également)
- enfin, ce que les gouvernements ne payent pas pour envoyer dans l'espace, ils ont des contrats avec ces entreprises privées.

Et ça ce sont juste 3 exemple. Tout ceci n'est que le début.
Si un satellite classique fait la taille d'un bus, désormais, on peut en faire de la taille d'une boîte à chaussures ou moins.

Après le secteur maritime (qui a placé nos villes depuis l'antiquité, qui a fondé nombre de forêts en France jusqu'à Louis XIV), le secteur de l'acier qui a permis les chemins de fer au XIX, celui de l'automobile, de l'aviation, de l'énergie, des ordinateurs et de l'internet, toutes ces choses ayant été fait par et au service des militaires avant des gens et des entreprises privées, c'est au tour de l'espace de le devenir. Get. Over. It.

https://www.youtube.com/watch?v=hiRBQxHrxNw