Come implementare la memoization in JavaScript

La memoization è una tecnica di ottimizzazione che consiste nel salvare i risultati di una funzione in base ai suoi argomenti, per riutilizzarli nelle chiamate successive senza doverli ricalcolare.

In JavaScript questa tecnica è particolarmente utile quando abbiamo funzioni pure e costose dal punto di vista computazionale, come algoritmi ricorsivi, elaborazioni numeriche o trasformazioni di dati pesanti.

Concetto di base della memoization

L'idea può essere riassunta in tre passi:

  1. Creare una struttura dati (cache) dove salvare i risultati calcolati.
  2. Quando la funzione viene chiamata, controllare se esiste già un risultato per quegli argomenti.
  3. Se il risultato esiste, restituirlo direttamente; altrimenti calcolarlo, salvarlo in cache e restituirlo.

In pseudo-codice: 


function memoizedF(args) {
  if (cache contiene args) {
    return cache[args];
  }
  const result = f(args);
  cache[args] = result;
  return result;
}

Una prima implementazione semplice

Partiamo da un caso semplice: una funzione che prende un solo argomento primitivo (numero o stringa). Useremo un oggetto come cache. 


function memoize(fn) {
  const cache = {};

  return function (arg) {
    if (arg in cache) {
      return cache[arg];
    }

    const result = fn(arg);
    cache[arg] = result;
    return result;
  };
}

Usiamola con una funzione costosa, ad esempio una versione ricorsiva della successione di Fibonacci. 


function slowFibonacci(n) {
  if (n <= 1) {
    return n;
  }
  return slowFibonacci(n - 1) + slowFibonacci(n - 2);
}

const memoizedFibonacci = memoize(slowFibonacci);

console.log(memoizedFibonacci(40)); // Prima volta: molto lenta
console.log(memoizedFibonacci(40)); // Seconda volta: istantanea

Alla prima chiamata con 40, la funzione esegue tutti i calcoli necessari. Alla seconda chiamata con lo stesso argomento, la funzione legge il risultato direttamente dalla cache.

Gestire più argomenti

Nella pratica, molte funzioni hanno più argomenti. Una strategia comune è quella di costruire una chiave univoca a partire dalla lista di argomenti, ad esempio usando JSON.stringify. 


function memoize(fn) {
  const cache = {};

  return function (...args) {
    const key = JSON.stringify(args);

    if (key in cache) {
      return cache[key];
    }

    const result = fn.apply(this, args);
    cache[key] = result;
    return result;
  };
}

Ora possiamo memoizzare funzioni con più parametri. 


function heavyComputation(a, b) {
  // Simuliamo qualcosa di costoso
  for (let i = 0; i < 1e8; i++) {}
  return a * b + a - b;
}

const memoizedHeavy = memoize(heavyComputation);

console.time("first");
console.log(memoizedHeavy(10, 20)); // Calcolo completo
console.timeEnd("first");

console.time("second");
console.log(memoizedHeavy(10, 20)); // Letto dalla cache
console.timeEnd("second");

La differenza di tempo tra la prima e la seconda chiamata può essere enorme, specialmente se la funzione è davvero costosa.

Usare Map invece di oggetti semplici

Gli oggetti JavaScript funzionano bene come cache, ma presentano alcune limitazioni. Una alternativa più robusta è usare Map.

  • Map permette chiavi di qualunque tipo, non solo stringhe.
  • Non ha collisioni con proprietà ereditate dalla prototype chain.
  • Offre metodi chiari come get, set e has.

function memoize(fn) {
  const cache = new Map();

  return function (...args) {
    const key = JSON.stringify(args);

    if (cache.has(key)) {
      return cache.get(key);
    }

    const result = fn.apply(this, args);
    cache.set(key, result);
    return result;
  };
}

Memoization con chiavi oggetto tramite Map annidate

Se vogliamo usare oggetti come chiave senza convertirli in stringhe, possiamo sfruttare Map o WeakMap annidate per mappare ogni argomento a un livello diverso. 


function memoizeWithObjectKeys(fn) {
  const cache = new Map();

  return function (...args) {
    let currentCache = cache;

    for (const arg of args) {
      if (!currentCache.has(arg)) {
        currentCache.set(arg, new Map());
      }
      currentCache = currentCache.get(arg);
    }

    if (currentCache.has("result")) {
      return currentCache.get("result");
    }

    const result = fn.apply(this, args);
    currentCache.set("result", result);
    return result;
  };
}

Questa tecnica evita di dover serializzare gli argomenti, a costo di gestire una struttura di cache un po' più complessa.

Usare WeakMap per evitare memory leak

Quando le chiavi sono oggetti che potrebbero non servire più, è utile usare WeakMap, che permette al garbage collector di liberare la memoria quando le chiavi non sono più referenziate altrove. 


function memoizeWithWeakMap(fn) {
  const cache = new WeakMap();

  return function (obj) {
    if (cache.has(obj)) {
      return cache.get(obj);
    }

    const result = fn.call(this, obj);
    cache.set(obj, result);
    return result;
  };
}

Questo approccio funziona bene per funzioni che accettano un singolo oggetto come argomento, ad esempio per calcolare e memorizzare proprietà derivate di un modello.

Memoization e funzioni asincrone

Possiamo memoizzare anche funzioni asincrone che restituiscono una Promise. In questo caso salveremo la promise nella cache. 


function memoizeAsync(fn) {
  const cache = new Map();

  return async function (...args) {
    const key = JSON.stringify(args);

    if (cache.has(key)) {
      return cache.get(key);
    }

    const promise = fn.apply(this, args);
    cache.set(key, promise);
    return promise;
  };
}

In questo modo, se la funzione viene chiamata più volte con gli stessi argomenti mentre la richiesta è ancora in corso, tutte le chiamate condivideranno la stessa promise.

Quando usare la memoization

La memoization non è sempre la scelta giusta. È particolarmente efficace quando:

  • La funzione è costosa da eseguire.
  • La funzione è deterministica: stessi argomenti, stesso risultato.
  • Gli argomenti non cambiano spesso o ci sono molte chiamate ripetute con gli stessi valori.
  • La memoria disponibile è sufficiente a mantenere in cache i risultati.

Non conviene invece memoizzare funzioni che:

  • Sono molto veloci rispetto al costo di gestione della cache.
  • Dipendono da effetti esterni (tempo, rete, stato globale) e non sono prevedibili.
  • Ricevono argomenti sempre diversi o molto variabili, riutilizzati raramente.

Limitare la dimensione della cache

Per evitare che la cache cresca indefinitamente, possiamo implementare una cache limitata. Un approccio semplice è quello di tenere al massimo maxSize elementi e cancellare il più vecchio. 


function memoizeWithLimit(fn, maxSize = 50) {
  const cache = new Map();

  return function (...args) {
    const key = JSON.stringify(args);

    if (cache.has(key)) {
      const value = cache.get(key);
      cache.delete(key);
      cache.set(key, value);
      return value;
    }

    const result = fn.apply(this, args);
    cache.set(key, result);

    if (cache.size > maxSize) {
      const firstKey = cache.keys().next().value;
      cache.delete(firstKey);
    }

    return result;
  };
}

Questo schema implementa una cache approssimativamente di tipo LRU (Least Recently Used): gli elementi usati più di recente restano in cache più a lungo.

Riassunto e best practice

Per usare la memoization in modo efficace in JavaScript, è utile tenere a mente alcuni principi:

  • Applicarla a funzioni pure e costose.
  • Usare Map o WeakMap quando le chiavi non sono semplici stringhe.
  • Evitare di serializzare oggetti grandi se non strettamente necessario.
  • Considerare un limite alla dimensione della cache per evitare consumi eccessivi di memoria.
  • Per funzioni asincrone, memoizzare le promise per evitare richieste duplicate.

Con queste tecniche puoi costruire facilmente utilità di memoization riusabili e adattarle alle esigenze della tua applicazione JavaScript, migliorando le prestazioni in modo pulito e controllato.

Torna su