La memoizzazione è una tecnica di programmazione che accelera le prestazioni memorizzando nella cache i valori restituiti da costose chiamate di funzione. Un “memorizzato” la funzione produrrà immediatamente un valore precalcolato se riceve input che è stato visto prima.
La memorizzazione è una forma specifica di memorizzazione nella cache che si presta a scenari in cui una funzione costosa viene eseguita ripetutamente, a volte con gli stessi argomenti. A condizione che la funzione sia pura in modo che produca sempre lo stesso valore da un particolare insieme di input, memorizzarla può aumentare l'efficienza e ridurre i cicli di CPU sprecati.
Molto spesso incontrerai la memoizzazione nei linguaggi di programmazione funzionali. La tecnica ha un'ampia utilità, però. È un concetto astratto che puoi incorporare in qualsiasi codice ricorsivo. Stiamo utilizzando JavaScript per questo articolo, ma potresti riscrivere gli esempi nella tua lingua di lavoro.
Un semplice esempio
Ecco 8217;una semplice funzione che genera il fattoriale di un dato intero:
const fattoriale = n => { se (n === 0) ritorno 1; altrimenti restituisce (fattoriale(n – 1) * n); };
Il calcolo fattoriale è ricorsivo, poiché factorial() chiama se stesso all'interno della condizione else. Anche il calcolo è puro, poiché qualsiasi dato valore di n restituirà sempre lo stesso valore. fattoriale(5) è 120, indipendentemente dallo stato del programma.
Pubblicità
A causa della natura ricorsiva della funzione, calcolare il fattoriale di diversi grandi numeri comporta operazioni inutili:
const x = fattoriale(100); const y = fattoriale(50);
Tutti i calcoli necessari per calcolare y sono già stati eseguiti come parte del calcolo di x. Se fattoriale() dovesse memorizzare nella cache i suoi input e gli output corrispondenti, il calcolo di y potrebbe essere notevolmente accelerato.
Memoizzazione della funzione fattoriale
Ecco un approccio di base che memorizza la funzione fattoriale():
const cache = { ;}; const fattoriale = n => { se (cache[n]) { cache di ritorno[n]; } lasciare valore; se (n === 0) valore = 1; altro valore = (fattoriale(n – 1) * n); cache[n] = valore; valore di ritorno; };
Ora, c'è un oggetto cache che factorial() usa per registrare i suoi valori di output. Ogni volta che viene chiamata la funzione, verifica prima se è stato visto in precedenza l'ingresso n. In caso affermativo, può andare in cortocircuito immediatamente e restituire il valore memorizzato nella cache. In caso contrario, il calcolo ricorsivo procede normalmente, ma le esecuzioni successive che utilizzano lo stesso numero verranno velocizzate.
Ora, il calcolo fattoriale(50) dopo fattoriale(100) sarà molto più efficiente. Il fattoriale di 50 verrebbe calcolato come parte del fattoriale di 100, quindi la funzione potrebbe restituire il valore quasi istantaneamente.
Una soluzione più generale
Mentre il codice sopra funziona, è specifico della funzione fattoriale(). Se stavi utilizzando altre funzioni simili, dovresti aggiungere manualmente il codice di memorizzazione nella cache a ciascuna di esse.
Una soluzione più generale ti permetterebbe di racchiudere qualsiasi funzione con una funzione di ordine superiore che fornisce il capacità di memorizzazione:
const memoize = fn => { const cache = {}; restituisce (…args) => { const argsString = JSON.stringify(args); se (!cache[argsString]) { cache[argsString] = fn(…arg); } restituisce la cache[argsString]; } };
Ora puoi regolare la funzione fattoriale() originale:
const fattoriale = memoize(n => { se (n === 0) ritorno 1; altrimenti restituisce (fattoriale(n – 1) * n); }); Pubblicità
Avvolgendo factorial() con memoize(), ottiene capacità di memoizzazione automatica. La funzione wrapper restituisce una nuova funzione che intercetta tutte le chiamate a factorial(), stringe i loro argomenti e controlla se sono stati visti prima. In caso affermativo, il valore restituito precedente viene riutilizzato senza chiamare affatto la funzione reale. Quando vengono visualizzati nuovi argomenti, la funzione viene invocata e il suo output viene aggiunto alla cache.
Il wrapper utilizza la sintassi dei parametri di riposo JavaScript per accettare un numero variabile di argomenti. Ciò significa che funzionerà con qualsiasi funzione JavaScript. Questo approccio utilizza JSON.stringify() per creare la rappresentazione di stringa degli argomenti, quindi è necessario prestare attenzione se si chiama una funzione con oggetti complessi, che non possono essere rappresentati completamente come JSON.
Quando non usare la memoizzazione?
La memorizzazione può fornire miglioramenti significativi delle prestazioni, in particolare per operazioni matematicamente pesanti. Tuttavia, non è una tecnica da usare ovunque. Non tutte le funzioni dovrebbero essere memorizzate, poiché in alcuni casi potresti finire per danneggiare le prestazioni.
Raccogliendo una funzione con memoize(), stai forzando un confronto degli argomenti di input ogni volta che quella funzione è chiamato. Questo di per sé consumerà un po' di tempo della CPU. Il wrapper di esempio sopra esegue JSON.stringify() ogni volta che viene chiamata la funzione, aggiungendo un nuovo sovraccarico.
La memorizzazione è appropriata per le funzioni in cui esiste un'alta probabilità che gli stessi valori di input vengano visualizzati regolarmente. Se chiamerai raramente una funzione con gli stessi argomenti, i riscontri nella cache saranno rari e potresti perdere le prestazioni per la serializzazione e il confronto degli argomenti. Il mantenimento della cache aumenta anche l'utilizzo della memoria, poiché tutti gli input e gli output precedenti devono essere conservati.
Dovresti, quindi, valutare completamente il ruolo di ciascuna funzione nel tuo programma prima di decidere di memorizzare. Confronta le prestazioni con e senza memorizzazione. A volte, può rivelarsi più vantaggioso fare affidamento sulle ottimizzazioni del browser.
Pubblicità
Infine, tieni presente che alcune funzioni non possono essere memorizzate. La tecnica funziona solo con funzioni pure—se la tua funzione raggiunge le variabili globali o qualche altro stato dell'applicazione, non dovrebbe essere memorizzata!
const functionUsingGlobalState = n => { se (n === window.scrollY) restituire vero; else funzione di ritornoUsingGlobalState(n – 1); }
Memorizzare la funzione sopra potrebbe produrre risultati imprevisti dopo la prima esecuzione. I valori di n verranno memorizzati nella cache utilizzando la versione originale di window.scrollY. Il wrapper di memoizzazione restituirà l'output memorizzato nella cache, anche se window.scrollY è cambiato.
Riepilogo
La memoizzazione è una forma di memorizzazione nella cache che accelera le prestazioni dei ricorsi ripetitivi operazioni. È una tecnica di programmazione funzionale che può essere implementata come wrapper generico per qualsiasi funzione pura.
Incontrerai più spesso la memoizzazione in funzioni chiamate di frequente che eseguono operazioni computazionalmente pesanti. Aiuta a evitare sprechi eliminando la necessità di ricalcolare i valori che sono già stati prodotti come parte di una chiamata precedente.
I vantaggi della memorizzazione saranno meno evidenti nelle funzioni che sono semplici all'inizio o chiamate raramente. In alcuni casi, l'uso improprio della memorizzazione può effettivamente danneggiare le prestazioni, quindi non memorizzare alla cieca ogni funzione nella tua applicazione.