des mots est parcourue en entier à chaque demande: pas tellement efficace.
On peut court-circuité tout ça grâce au binary search. Cela fonctionne comme suit:
L'exemple classique est le jeu de devinette-enfant. Je choisis un chiffre de 1 à 100 que l'autre doit deviner; à chaque essai, je lui dis s'il se trouve trop haut ou trop bas. D'un point de vue
strictement mathématique, le joueur devient plus efficace s'il procède par tranches de division
par 2.
Le dico s'améliore s'il consulte des lattes de mots qui rétrécissent de facteur 2 à chaque tour.
On amende aussi la reconnaissance des mots par la précédence lexicographique; le programme
revoit chaque lettre d'un mot, et peut nous informer mi-mot si on est rendu trop loin.
En gardant la forme du dico tel quel, on échange areEqual pour compareStrings et on embarque
une nouvelle fonction lookup.
En comparant dico et search, si dico a une valeur moindre (qui veut dire vient avant), cela
renvoit -1. Égalité renvoit 0, et valeur plus (vient après) 1. Quand low est plus grand que high (on a tout épuisé), le mot ne figure pas.
Sur une banque de 100 000 mots, le gain de performance devient nécessaire.
Aucun commentaire:
Enregistrer un commentaire