Comment utiliser Memoize pour mettre en cache les résultats de la fonction JavaScript et accélérer votre code

Les fonctions font partie intégrante de la programmation. Ils aident à ajouter de la modularité et de la réutilisabilité à notre code.

Il est assez courant de diviser notre programme en morceaux en utilisant des fonctions que nous pouvons appeler plus tard pour effectuer des actions utiles.

Parfois, une fonction peut devenir coûteuse à appeler plusieurs fois (par exemple, une fonction pour calculer la factorielle d'un nombre). Mais il existe un moyen d'optimiser ces fonctions et de les faire s'exécuter beaucoup plus rapidement: la mise en cache .

Par exemple, disons que nous avons a functionpour renvoyer la factorielle d'un nombre:

function factorial(n) { // Calculations: n * (n-1) * (n-2) * ... (2) * (1) return factorial }

Génial, trouvons maintenant factorial(50). L'ordinateur effectuera des calculs et nous rendra la réponse finale, chérie!

Quand c'est fait, trouvons factorial(51). L'ordinateur effectue à nouveau un certain nombre de calculs et nous donne le résultat, mais vous avez peut-être remarqué que nous répétons déjà un certain nombre d'étapes qui auraient pu être évitées. Une manière optimisée serait:

factorial(51) = factorial(50) * 51

Mais notre functioneffectue les calculs à partir de zéro chaque fois qu'il est appelé:

factorial(51) = 51 * 50 * 49 * ... * 2 * 1

Ne serait-il pas cool que notre factorialfonction puisse se souvenir des valeurs de ses calculs précédents et les utiliser pour accélérer l'exécution?

Vient la mémorisation , un moyen pour nous functionde mémoriser (mettre en cache) les résultats. Maintenant que vous avez une compréhension de base de ce que nous essayons de réaliser, voici une définition formelle:

La mémorisation est une technique d'optimisation utilisée principalement pour accélérer les programmes informatiques en stockant les résultats d'appels de fonction coûteux et en renvoyant le résultat en cache lorsque les mêmes entrées se produisent

Mémoriser en termes simples signifie mémoriser ou stocker en mémoire. Une fonction mémorisée est généralement plus rapide car si la fonction est appelée ultérieurement avec la ou les valeurs précédentes, alors au lieu d'exécuter la fonction, nous allons chercher le résultat dans le cache.

Voici à quoi pourrait ressembler une simple fonction mémorisée (et voici un CodePen au cas où vous voudriez interagir avec lui) :

// a simple function to add something const add = (n) => (n + 10); add(9); // a simple memoized function to add something const memoizedAdd = () => { let cache = {}; return (n) => { if (n in cache) { console.log('Fetching from cache'); return cache[n]; } else { console.log('Calculating result'); let result = n + 10; cache[n] = result; return result; } } } // returned function from memoizedAdd const newAdd = memoizedAdd(); console.log(newAdd(9)); // calculated console.log(newAdd(9)); // cached

Mémorisation à emporter

Quelques points à retenir du code ci-dessus sont:

  • memoizedAddrenvoie un functionqui est appelé plus tard. Cela est possible car en JavaScript, les fonctions sont des objets de première classe qui nous permettent de les utiliser comme des fonctions d'ordre supérieur et de renvoyer une autre fonction.
  • cachepeut se souvenir de ses valeurs car la fonction retournée a une fermeture dessus.
  • Il est essentiel que la fonction mémorisée soit pure. Une fonction pure renverra la même sortie pour une entrée particulière, peu importe le nombre de fois qu'elle est appelée, ce qui rend le cachetravail comme prévu.

Écrire votre propre memoizefonction

Le code précédent fonctionne bien mais que se passe-t-il si nous voulions transformer une fonction en fonction mémorisée?

Voici comment écrire votre propre fonction de mémorisation (codepen):

// a simple pure function to get a value adding 10 const add = (n) => (n + 10); console.log('Simple call', add(3)); // a simple memoize function that takes in a function // and returns a memoized function const memoize = (fn) => { let cache = {}; return (...args) => { let n = args[0]; // just taking one argument here if (n in cache) { console.log('Fetching from cache'); return cache[n]; } else { console.log('Calculating result'); let result = fn(n); cache[n] = result; return result; } } } // creating a memoized function for the 'add' pure function const memoizedAdd = memoize(add); console.log(memoizedAdd(3)); // calculated console.log(memoizedAdd(3)); // cached console.log(memoizedAdd(4)); // calculated console.log(memoizedAdd(4)); // cached

Maintenant c'est génial! Cette memoizefonction simple functionencapsulera n'importe quel simple dans un équivalent mémorisé. Le code fonctionne bien pour des fonctions simples et il peut être facilement modifié pour gérer un nombre illimité de argumentsfonctions selon vos besoins. Une autre alternative consiste à utiliser certaines bibliothèques de facto telles que:

  • Lodash _.memoize(func, [resolver])
  • @memoizeDécorateurs ES7 de decko

Mémorisation des fonctions récursives

Si vous essayez de passer une fonction récursive à la memoizefonction ci-dessus ou à _.memoizepartir de Lodash, les résultats ne seront pas comme prévu car la fonction récursive lors de ses appels ultérieurs finira par s'appeler elle-même au lieu de la fonction mémorisée, n'utilisant ainsi pas le cache.

Assurez-vous simplement que votre fonction récursive appelle la fonction mémorisée. Voici comment modifier un exemple factoriel de manuel (codepen):

// same memoize function from before const memoize = (fn) => { let cache = {}; return (...args) => { let n = args[0]; if (n in cache) { console.log('Fetching from cache', n); return cache[n]; } else { console.log('Calculating result', n); let result = fn(n); cache[n] = result; return result; } } } const factorial = memoize( (x) => { if (x === 0) { return 1; } else { return x * factorial(x - 1); } } ); console.log(factorial(5)); // calculated console.log(factorial(6)); // calculated for 6 and cached for 5

Quelques points à noter à partir de ce code:

  • La factorialfonction appelle récursivement une version mémorisée d'elle-même.
  • La fonction mémorisée met en cache les valeurs des factorielles précédentes, ce qui améliore considérablement les calculs puisqu'ils peuvent être réutilisés factorial(6) = 6 * factorial(5)

La mémorisation est-elle identique à la mise en cache?

Oui, en quelque sorte. La mémorisation est en fait un type spécifique de mise en cache. Alors que la mise en cache peut faire référence en général à n'importe quelle technique de stockage (comme la mise en cache HTTP) pour une utilisation future, la mémorisation implique spécifiquement la mise en cache des valeurs de retour d'un function.

Quand mémoriser vos fonctions

Bien qu'il puisse sembler que la mémorisation puisse être utilisée avec toutes les fonctions, elle a en fait des cas d'utilisation limités:

  • Afin de mémoriser une fonction, elle doit être pure afin que les valeurs de retour soient les mêmes pour les mêmes entrées à chaque fois
  • La mémorisation est un compromis entre l'espace supplémentaire et la vitesse ajoutée et n'est donc significative que pour les fonctions ayant une plage d'entrée limitée afin que les valeurs mises en cache puissent être utilisées plus fréquemment
  • Il peut sembler que vous devriez mémoriser vos appels API, mais ce n'est pas nécessaire car le navigateur les met automatiquement en cache pour vous. Voir la mise en cache HTTP pour plus de détails
  • Le meilleur cas d'utilisation que j'ai trouvé pour les fonctions mémorisées concerne les fonctions de calcul lourdes qui peuvent améliorer considérablement les performances (factorielle et fibonacci ne sont pas vraiment de bons exemples du monde réel)
  • Si vous êtes dans React / Redux, vous pouvez vérifier reselect qui utilise un sélecteur mémorisé pour vous assurer que les calculs ne se produisent que lorsqu'un changement se produit dans une partie liée de l'arborescence d'état.

Lectures complémentaires

The following links can be useful if you would like to know more about some of the topics from this article in more detail:

  • Higher order functions in JavaScript
  • Closures in JavaScript
  • Pure functions
  • Lodash’s _.memoize docs and source code
  • More memoization examples here and here
  • reactjs/reselect

I hope this article was useful for you, and you’ve gained a better understanding of memoization in JavaScript :)

You may follow me on twitter for latest updates. I've also started posting more recent posts on my personal blog.