La mémorisation est une technique de programmation qui accélère les performances en mettant en cache les valeurs de retour des appels de fonction coûteux. Un “mémorisé” fonction produira immédiatement une valeur précalculée si elle reçoit des entrées qu'elle a déjà vues.
La mémorisation est une forme spécifique de mise en cache qui se prête à des scénarios où une fonction coûteuse est exécutée à plusieurs reprises, parfois avec les mêmes arguments. À condition que la fonction soit pure de sorte qu'elle produise toujours la même valeur à partir d'un ensemble particulier d'entrées, la mémoriser peut augmenter l'efficacité et réduire les cycles CPU gaspillés.
Vous rencontrerez le plus souvent la mémorisation dans les langages de programmation fonctionnels. La technique a une large utilité, cependant. C'est un concept abstrait que vous pouvez incorporer dans n'importe quel code récursif. Nous utilisons JavaScript pour cet article, mais vous pouvez réécrire les exemples dans votre langue de travail.
Un exemple simple
Ici&# 8217;s une fonction simple qui génère la factorielle d'un entier donné :
const factorial = n => { si (n === 0) retour 1 ; sinon renvoie (factoriel(n – 1) * n); };
Le calcul factoriel est récursif, car factorial() s'appelle dans la condition else. Le calcul est également pur, car toute valeur donnée de n renverra toujours la même valeur. factorial(5) vaut 120, quel que soit l'état du programme.
Publicité
En raison de la nature récursive de la fonction, le calcul de la factorielle de plusieurs grands nombres entraîne des opérations inutiles :
const x = factoriel(100); const y = factoriel(50);
Tous les calculs nécessaires pour calculer y ont déjà été effectués dans le cadre du calcul de x. Si factorial() mettait en cache ses entrées et leurs sorties correspondantes, le calcul de y pourrait être considérablement accéléré.
Mémorisation de la fonction factorielle
Voici une approche de base qui mémorise la fonction factorielle() :
const cache = { ;}; factorielle const = n => { si (cache[n]) { cache de retour[n]; } laisser la valeur; si (n === 0) valeur = 1 ; sinon valeur = (factorielle(n – 1) * n); cache[n] = valeur ; valeur de retour ; };
Maintenant, il y a un objet cache que factorial() utilise pour enregistrer ses valeurs de sortie. Chaque fois que la fonction est appelée, elle vérifie d'abord si elle a déjà vu l'entrée n. Si c'est le cas, il peut immédiatement court-circuiter et renvoyer la valeur mise en cache. Sinon, le calcul récursif se déroule normalement, mais les exécutions suivantes utilisant le même nombre seront accélérées.
Maintenant, le calcul factoriel (50) après factoriel (100) sera beaucoup plus efficace. La factorielle de 50 serait calculée dans le cadre de la factorielle de 100, de sorte que la fonction pourrait renvoyer la valeur presque instantanément.
Une solution plus générale
Bien que le code ci-dessus fonctionne, il est spécifique à la fonction factorial(). Si vous utilisiez d'autres fonctions similaires, vous auriez besoin d'ajouter manuellement le code de mise en cache à chacune.
Une solution plus générale vous permettrait d'envelopper n'importe quelle fonction avec une fonction d'ordre supérieur qui fournit le capacité de mémorisation :
const memoize = fn => { cache const = {}; renvoie (…args) => { const argsString = JSON.stringify(args); si (!cache[argsString]) { cache[argsString] = fn(…args); } cache de retour[argsString]; } };
Maintenant, vous pouvez ajuster la fonction factorial() d'origine :
const factorial = memoize(n => { si (n === 0) retour 1 ; sinon renvoie (factoriel(n – 1) * n); }); Publicité
En enveloppant factorial() avec memoize(), il obtient des capacités de mémorisation automatique. La fonction wrapper renvoie une nouvelle fonction qui intercepte tous les appels à factorial(), stringifie leurs arguments et vérifie s'ils ont déjà été vus. Si c'est le cas, la valeur de retour précédente est réutilisée sans appeler du tout la fonction réelle. Lorsque de nouveaux arguments sont vus, la fonction est invoquée et sa sortie est ajoutée au cache.
Le wrapper utilise la syntaxe des paramètres de repos JavaScript pour accepter un nombre variable d'arguments. Cela signifie qu'il fonctionnera avec n'importe quelle fonction JavaScript. Cette approche utilise JSON.stringify() pour créer la représentation sous forme de chaîne des arguments, il faut donc faire attention si vous appelez une fonction avec des objets complexes, qui ne peuvent pas être entièrement représentés en tant que JSON.
Quand ne pas utiliser la mémorisation ?
La mémorisation peut apporter des améliorations significatives des performances, en particulier pour les opérations mathématiquement lourdes. Ce n'est pas une technique à utiliser partout, cependant. Toutes les fonctions ne doivent pas être mémorisées, car vous pourriez finir par nuire aux performances dans certains cas.
En enveloppant une fonction avec memoize(), vous forcez une comparaison des arguments d'entrée à chaque fois que cette fonction est appelé. Cela en soi consommera du temps CPU. L'exemple de wrapper ci-dessus exécute JSON.stringify() chaque fois que la fonction est appelée, ajoutant une nouvelle surcharge.
La mémorisation est appropriée pour les fonctions où il y a de fortes chances que les mêmes valeurs d'entrée soient vues régulièrement. Si vous appelez rarement une fonction avec les mêmes arguments, les accès au cache seront peu fréquents et vous risquez de perdre des performances en raison de la sérialisation et de la comparaison des arguments. Le maintien du cache augmente également l'utilisation de la mémoire, car toutes les entrées et sorties précédentes doivent être conservées.
Vous devez donc bien évaluer le rôle de chaque fonction dans votre programme avant de décider de mémoriser. Comparez les performances avec et sans mémorisation. Parfois, il peut s'avérer plus avantageux de s'appuyer sur les propres optimisations du navigateur.
Publicité
Enfin, gardez à l'esprit que certaines fonctions ne peuvent pas être mémorisées. La technique ne fonctionne qu'avec des fonctions pures—si votre fonction atteint des variables globales ou un autre état de l'application, elle ne doit pas être mémorisée !
const functionUsingGlobalState = n => { si (n === window.scrollY) renvoie vrai ; sinon renvoie functionUsingGlobalState(n – 1); }
La mémorisation de la fonction ci-dessus peut donner des résultats inattendus après la première exécution. Les valeurs de n seront mises en cache à l'aide de la version originale de window.scrollY. Le wrapper de mémorisation renverra la sortie mise en cache, même si window.scrollY a changé.
Résumé
La mémorisation est une forme de mise en cache qui accélère les performances de récursivité répétitive opérations. C'est une technique de programmation fonctionnelle qui peut être implémentée en tant que wrapper générique pour n'importe quelle fonction pure.
Vous rencontrerez le plus souvent la mémorisation dans les fonctions fréquemment appelées qui effectuent des opérations lourdes en calcul. Cela permet d'éviter le gaspillage en supprimant le besoin de recalculer des valeurs qui ont déjà été produites dans le cadre d'un appel précédent.
Les avantages de la mémorisation seront moins apparents dans les fonctions simples au départ ou appelées peu fréquemment. Dans certains cas, une mauvaise utilisation de la mémorisation peut nuire aux performances, alors ne mémorisez pas aveuglément chaque fonction de votre application.