Il existe plusieurs excellents articles qui parlent de la technique d’optimisation appelée mémorisation. Vous pouvez y accéder ici et ici. Ce que nous allons faire, c’est vous donner un bref aperçu de ce qu’est la mémoïsation. Nous irons un peu plus loin en effectuant une analyse pas à pas de ce que le code « mémorisant » fait réellement, ligne par ligne. À la fin de l’article, vous comprendrez parfaitement la mémoïsation.

La mémoïsation est la pratique programmatique consistant à faire en sorte que les longues fonctions récursives/itératives s’exécutent beaucoup plus rapidement.

Comment, demandez-vous ? En mettant en cache les valeurs que la fonction renvoie après son exécution initiale.

Lorsque nous entrons la même valeur dans notre fonction mémorisée, elle renvoie la valeur stockée dans le cache au lieu d’exécuter la fonction à nouveau, ce qui augmente les performances. Votre programme n’a plus besoin de recalculer chaque nombre pour obtenir un résultat.

Ça a l’air génial, non ? Eh bien, ce qui est encore mieux, c’est qu’il n’est pas difficile de comprendre ce que fait une fonction memoize une fois que vous décomposez le code.

Voici un exemple d’une fonction memo de base:

Commençons par le début…

Nous retournons ce qu’on appelle une fermeture anonyme. Notre fermeture anonyme est capable d’hériter de toute variable ou, dans ce cas, de toute fonction passée dans memo. Nous pouvons alors jouer avec l’objet arguments que notre fonction passée fournit.

Note complémentaire : Donc, si chaque fonction a un objet arguments, pourquoi n’héritons-nous pas de l’objet arguments de memo ? C’est parce que, en règle générale, les fermetures n’héritent pas de l’objet arguments d’une fonction externe. Nous utilisons cette règle à notre avantage afin de jouer avec la fonction que nous voulons mémoriser.

Décomposons exactement ce que fait la mémorisation en regardant un exemple très simple et peu pratique. En passant, vous devriez copier/coller ce code, ou n’importe quel code d’ailleurs, pour vraiment avoir une idée de la façon dont cela fonctionne.

Je pense que nous avons compris l’essentiel de cet exemple de code. Il parle pratiquement de lui-même. Etoffons-le un peu plus en regardant un instantané de notre vraie fonction mémo :

Maintenant que nous avons décomposé ce que fait une fonction mémo, créons une expression de fonction et passons une fonction Fibonacci récursive dans memo et voyons ce qui se passe.

//Now we'll test our code!
// =======TEST=======
fib(10)//On the first try we need to load//=> loading…//=> loading…//=> loading…//=> loading…//=> loading…//=> 4 loadings later we get...//=> 89// And on the second try…fib(10)//=> 89//No loading! Yaay!//The cool thing about memoizing the recursive Fibonacci algorithm is that once we make a call for the value of the nth number in the series, we are able to store all the previous numbers in the series.//So if we try...
fib(7) //=> 21
//We don't have to recalculate anything.//And if we want to try fib(11)...
fib(11)
//loading...
//=> 144
//Our memoized recursive function already cached fib(1-10),so all it needed to do was to calculate the cached values. // This is what the cache now looks like:
/*
{ '{"0":0}': 1,
'{"0":1}': 1,
'{"0":2}': 2,
'{"0":3}': 3,
'{"0":4}': 5,
'{"0":5}': 8,
'{"0":6}': 13,
'{"0":7}': 21,
'{"0":8}': 34,
'{"0":9}': 55,
'{"0":10}': 89,
'{"0":11}': 144}
*/

Conclusion

La mémorisation devient démystifiée lorsque vous la réduisez à des paires clé-valeur. Tout ce que nous faisons est de créer un objet, de vérifier les valeurs existantes qui correspondent à l’entrée de l’utilisateur, et de stocker de nouvelles paires clé-valeur si elles n’existent pas dans notre objet.

Bien sûr, stocker toutes ces données signifie que nous allons utiliser de la mémoire. Il est préférable d’implémenter la mémorisation sur des fonctions qui sont pures et qui impliquent des calculs lourds et répétitifs.

Bonus:

Juste pour le plaisir, voici une version fonctionnelle de notre mémoizer:

.