Memoization JavaScript
Edoardo Midali
La memoization è una tecnica di ottimizzazione che consiste nel memorizzare i risultati di chiamate di funzione costose per evitare di ripetere gli stessi calcoli. Quando una funzione memoizzata viene chiamata con gli stessi parametri, invece di rieseguire il calcolo, restituisce il risultato precedentemente memorizzato. Questa tecnica è particolarmente efficace per funzioni pure con calcoli intensivi o chiamate ricorsive.
Principi della Memoization
La memoization si basa su un concetto semplice: se una funzione è pura (restituisce sempre lo stesso output per lo stesso input senza effetti collaterali), possiamo sostituire i calcoli ripetuti con lookup in memoria. Il trade-off è tra utilizzo di memoria (per conservare i risultati) e tempo di calcolo (per evitare computazioni ripetute).
// Funzione costosa senza memoization
function fibonacci(n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
// Questa chiamata richiede molto tempo per valori alti
console.time("fibonacci(40)");
console.log(fibonacci(40)); // 102334155
console.timeEnd("fibonacci(40)"); // ~1000ms
// Con memoization
function fibonacciMemo(n, cache = {}) {
if (n in cache) return cache[n];
if (n <= 1) return n;
cache[n] = fibonacciMemo(n - 1, cache) + fibonacciMemo(n - 2, cache);
return cache[n];
}
console.time("fibonacciMemo(40)");
console.log(fibonacciMemo(40)); // 102334155
console.timeEnd("fibonacciMemo(40)"); // ~1ms
Implementazioni di Base
Memoization Manuale
function calcoloComplesso(x, y, z) {
// Simulazione calcolo intensivo
console.log(`Calcolando per ${x}, ${y}, ${z}`);
let risultato = 0;
for (let i = 0; i < 1000000; i++) {
risultato += Math.sin(x) * Math.cos(y) * Math.tan(z);
}
return risultato;
}
// Versione memoizzata
function calcoloComplessoMemo() {
const cache = new Map();
return function (x, y, z) {
const chiave = `${x},${y},${z}`;
if (cache.has(chiave)) {
console.log("Risultato dalla cache");
return cache.get(chiave);
}
const risultato = calcoloComplesso(x, y, z);
cache.set(chiave, risultato);
return risultato;
};
}
const calcoloMemo = calcoloComplessoMemo();
// Prima chiamata: calcolo effettivo
calcoloMemo(1, 2, 3); // "Calcolando per 1, 2, 3"
// Seconda chiamata: dalla cache
calcoloMemo(1, 2, 3); // "Risultato dalla cache"
Funzione Generica di Memoization
function memoize(fn) {
const cache = new Map();
return function (...args) {
const chiave = JSON.stringify(args);
if (cache.has(chiave)) {
return cache.get(chiave);
}
const risultato = fn.apply(this, args);
cache.set(chiave, risultato);
return risultato;
};
}
// Utilizzo
const fattorialeLento = function (n) {
if (n <= 1) return 1;
return n * fattorialeLento(n - 1);
};
const fattorialeVeloce = memoize(fattorialeLento);
console.time("fattoriale(10)");
fattorialeVeloce(10); // Prima chiamata
console.timeEnd("fattoriale(10)");
console.time("fattoriale(10) cached");
fattorialeVeloce(10); // Dalla cache
console.timeEnd("fattoriale(10) cached");
Gestione Avanzata della Cache
Cache con TTL (Time To Live)
function memoizeWithTTL(fn, ttl = 60000) {
// TTL in millisecondi
const cache = new Map();
return function (...args) {
const chiave = JSON.stringify(args);
const ora = Date.now();
if (cache.has(chiave)) {
const { valore, timestamp } = cache.get(chiave);
if (ora - timestamp < ttl) {
return valore;
} else {
cache.delete(chiave); // Cache scaduta
}
}
const risultato = fn.apply(this, args);
cache.set(chiave, { valore: risultato, timestamp: ora });
return risultato;
};
}
// API call con cache di 5 minuti
const fetchUserData = memoizeWithTTL(async function (userId) {
const response = await fetch(`/api/users/${userId}`);
return response.json();
}, 5 * 60 * 1000);
Cache con Limite di Dimensione (LRU)
class LRUMemoizer {
constructor(fn, maxSize = 100) {
this.fn = fn;
this.maxSize = maxSize;
this.cache = new Map();
}
memoized(...args) {
const chiave = JSON.stringify(args);
if (this.cache.has(chiave)) {
// Sposta in fondo (più recente)
const valore = this.cache.get(chiave);
this.cache.delete(chiave);
this.cache.set(chiave, valore);
return valore;
}
// Se cache piena, rimuovi il meno recente
if (this.cache.size >= this.maxSize) {
const primaChiave = this.cache.keys().next().value;
this.cache.delete(primaChiave);
}
const risultato = this.fn.apply(this, args);
this.cache.set(chiave, risultato);
return risultato;
}
clear() {
this.cache.clear();
}
size() {
return this.cache.size;
}
}
// Utilizzo
const memoizer = new LRUMemoizer(calcoloComplesso, 50);
const calcoloLRU = (...args) => memoizer.memoized(...args);
Memoization per Chiamate Asincrone
Promise Memoization
function memoizeAsync(asyncFn) {
const cache = new Map();
return function (...args) {
const chiave = JSON.stringify(args);
if (cache.has(chiave)) {
return cache.get(chiave);
}
const promise = asyncFn.apply(this, args).catch((error) => {
// Rimuovi dalla cache se la promise fallisce
cache.delete(chiave);
throw error;
});
cache.set(chiave, promise);
return promise;
};
}
// API call memoizzata
const fetchData = memoizeAsync(async function (url) {
console.log(`Fetching ${url}`);
const response = await fetch(url);
if (!response.ok) throw new Error("Network error");
return response.json();
});
// Utilizzo
async function esempio() {
try {
// Prima chiamata: fetch effettivo
const data1 = await fetchData("/api/data");
// Seconda chiamata: stessa promise dalla cache
const data2 = await fetchData("/api/data");
console.log(data1 === data2); // true - stessa promise
} catch (error) {
console.error("Errore:", error);
}
}
Debounced Memoization
function memoizeWithDebounce(fn, delay = 300) {
const cache = new Map();
const timeouts = new Map();
return function (...args) {
const chiave = JSON.stringify(args);
// Cancella timeout precedente per questa chiave
if (timeouts.has(chiave)) {
clearTimeout(timeouts.get(chiave));
}
// Se abbiamo già il risultato, restituiscilo
if (cache.has(chiave)) {
return cache.get(chiave);
}
return new Promise((resolve, reject) => {
const timeoutId = setTimeout(() => {
try {
const risultato = fn.apply(this, args);
cache.set(chiave, risultato);
timeouts.delete(chiave);
resolve(risultato);
} catch (error) {
timeouts.delete(chiave);
reject(error);
}
}, delay);
timeouts.set(chiave, timeoutId);
});
};
}
// Ricerca con debouncing e memoization
const search = memoizeWithDebounce(function (query) {
console.log(`Searching for: ${query}`);
return fetch(`/api/search?q=${query}`).then((r) => r.json());
}, 500);
Casi d’Uso Pratici
Caching di Componenti React
import React, { useMemo } from "react";
// Memoization con React.memo per componenti
const ExpensiveComponent = React.memo(function ExpensiveComponent({
data,
config,
}) {
const processedData = useMemo(() => {
console.log("Processing data...");
return data.map((item) => ({
...item,
processed: true,
hash: config.algorithm(item.value),
}));
}, [data, config.algorithm]);
return (
<div>
{processedData.map((item) => (
<div key={item.id}>
{item.value} - {item.hash}
</div>
))}
</div>
);
});
// Hook personalizzato con memoization
function useExpensiveCalculation(input, dependencies) {
return useMemo(() => {
console.log("Expensive calculation...");
return heavyComputation(input);
}, dependencies);
}
Memoization per Validazione Forms
const validatorMemo = memoize(function validateField(value, rules) {
console.log(`Validating: ${value}`);
for (const rule of rules) {
if (!rule.test(value)) {
return { valid: false, error: rule.message };
}
}
return { valid: true, error: null };
});
// Regole di validazione
const emailRules = [
{ test: (v) => v.length > 0, message: "Email richiesta" },
{ test: (v) => v.includes("@"), message: "Email non valida" },
{ test: (v) => v.length < 100, message: "Email troppo lunga" },
];
// Utilizzo
const result1 = validatorMemo("test@email.com", emailRules); // Calcolo
const result2 = validatorMemo("test@email.com", emailRules); // Cache
Considerazioni e Limitazioni
Memoria vs Performance: La memoization aumenta l’utilizzo di memoria. È importante bilanciare i benefici in termini di performance con il costo in memoria, specialmente per applicazioni con vincoli di memoria.
Serializzazione delle Chiavi: L’uso di JSON.stringify per creare chiavi di cache può essere problematico con oggetti complessi o circolari. Considera librerie specializzate per la serializzazione o chiavi personalizzate.
Funzioni Pure: La memoization funziona solo con funzioni pure. Funzioni con effetti collaterali o che dipendono da stato esterno possono produrre risultati incorretti.
Invalidation Strategy: In applicazioni complesse, potresti aver bisogno di strategie per invalidare la cache quando i dati sottostanti cambiano.
// Esempio di invalidazione intelligente
class SmartMemoizer {
constructor(fn) {
this.fn = fn;
this.cache = new Map();
this.dependencies = new Set();
}
memoized(...args) {
const chiave = JSON.stringify(args);
if (this.cache.has(chiave)) {
return this.cache.get(chiave);
}
const risultato = this.fn.apply(this, args);
this.cache.set(chiave, risultato);
return risultato;
}
invalidate(pattern) {
for (const chiave of this.cache.keys()) {
if (chiave.includes(pattern)) {
this.cache.delete(chiave);
}
}
}
clearAll() {
this.cache.clear();
}
}
La memoization è una tecnica potente che può drasticamente migliorare le performance di applicazioni con calcoli ripetitivi. Tuttavia, va applicata con giudizio, considerando sempre il trade-off tra memoria e performance e assicurandosi che sia appropriata per il caso d’uso specifico.
