Mémoïsation en JavaScript : garder un résultat déjà calculé au lieu de le refaire

Un calcul coûteux appelé cent fois avec les mêmes arguments produit cent fois le même résultat. Le refaire à chaque appel est du travail perdu.

La mémoïsation applique une idée élémentaire : garder la réponse la première fois, la ressortir ensuite. Le gain peut faire passer un calcul de plusieurs secondes à quelques microsecondes.

Définition

La mémoïsation consiste à stocker le résultat d'une fonction dans un cache indexé par ses arguments. Au prochain appel avec les mêmes valeurs, la fonction n'est pas exécutée : le cache répond à sa place.

function memoise(fonction) {
  const cache = new Map();

  return function (argument) {
    if (cache.has(argument)) return cache.get(argument);
    const resultat = fonction(argument);
    cache.set(argument, resultat);
    return resultat;
  };
}

let appels = 0;
const carre = memoise((n) => {
  appels += 1;
  return n * n;
});

console.log(carre(12), carre(12), appels); // 144 144 1

Le cache vit dans une Closure (fermeture) : il n'est accessible que par la fonction renvoyée, et il survit d'un appel à l'autre. La Map accepte n'importe quel type de clé, y compris un objet.

Fibonacci, la démonstration qui frappe

Une Récursivité naïve recalcule les mêmes valeurs des milliers de fois. Le compteur d'appels le montre sans discussion.

let brut = 0;
function fibo(n) {
  brut += 1;
  return n < 2 ? n : fibo(n - 1) + fibo(n - 2);
}
fibo(25);
console.log(brut); // 242785

const cache = new Map();
let rapide = 0;
function fiboMemo(n) {
  rapide += 1;
  if (cache.has(n)) return cache.get(n);
  const valeur = n < 2 ? n : fiboMemo(n - 1) + fiboMemo(n - 2);
  cache.set(n, valeur);
  return valeur;
}
fiboMemo(25);
console.log(rapide); // 49

242 785 appels contre 49, pour un résultat identique. Le rapport dépasse quatre mille, et il grandit encore avec la valeur demandée.

Quand ne pas mémoïser

• Quand la fonction n'est pas pure. Si le résultat dépend de l'heure ou d'un état extérieur, le cache renvoie une réponse périmée. Voir Fonction pure.
• Quand les arguments ne se répètent pas. Le cache grossit sans jamais servir.
• Quand le calcul est déjà court. Consulter le cache coûte parfois plus que refaire l'opération.

Questions fréquentes

La solution courante est de fabriquer une clé unique, souvent avec JSON.stringify(arguments). Elle fonctionne, mais elle a un coût, et l'ordre des clés d'un objet change la chaîne obtenue. Pour deux ou trois arguments simples, une concaténation avec un séparateur improbable reste plus rapide et plus prévisible.

La portée et la durée de vie. Une mémoïsation vit dans la mémoire du processus ou de l'onglet, disparaît au rechargement, et n'est jamais partagée entre utilisateurs. Un cache serveur survit aux requêtes et sert plusieurs clients, au prix d'une invalidation à gérer explicitement.

Le principe est identique, avec une nuance : leur cache ne garde en général qu'une seule entrée, celle du dernier appel, et se vide dès que les dépendances changent. Notre formation React montre où ce réflexe aide réellement, et où il ajoute du code sans rien accélérer.