Programmazione funzionale in JavaScript: La memorizzazione

X

Privacy e cookie

Questo sito utilizza i cookie. Continuando, accettate il loro utilizzo. Per saperne di più, ad esempio, su come controllare i cookie.

Capito

8540563633_e4baebcb26_c

Immagine di Lori-B.

Il viaggio arriva alla fine. Con quest’ultima voce sull’ottimizzazione mettiamo fine alla serie sulla programmazione funzionale.

Se nella penultima puntata abbiamo introdotto i problemi della programmazione funzionale in termini di prestazioni, oggi parlerò di un meccanismo che può aiutarci ad evitare calcoli e valutazioni inutili: la memorizzazione. Un termine profondamente radicato in questo stile di programmazione.

Se sei con me da ottobre, non credo che tu voglia perdere quest’ultima voce. Concludiamo bene:

Caching dei risultati

Come abbiamo detto, uno dei problemi della programmazione funzionale era causato dall’uso intensivo delle funzioni, abbiamo visto che più calcoli avevamo bisogno in un sistema, maggiore era la possibilità di far sì che lo stack di contesto potesse superare e lasciarci appesi.

Abbiamo visto che la valutazione pigra potrebbe evitare chiamate inutili, tuttavia è un sistema abbastanza limitato e che non causa tempi di miglioramento spettacolari. Se ci pensiamo bene a freddo sarebbe bello avere qualche meccanismo che ci permetta di mettere in cache i risultati che sono già stati calcolati.

In alcuni linguaggi di programmazione questo caching dei risultati è fatto nativamente dai compilatori, tuttavia, in linguaggi come JavaScript o Python questo caching dei risultati deve essere gestito manualmente.

L’idea del caching è di sfruttare la trasparenza referenziale per evitare calcoli inutili. Se sappiamo che una funzione genera sempre gli stessi risultati per determinati parametri, possiamo eseguire quella funzione, tutte le volte che vogliamo ottenendo che il risultato non cambi. Se è così, potremmo pensare che non sarebbe necessario calcolare i risultati tutto il tempo se sappiamo già quale valore sarà ottenuto.

Ecco perché, potremmo generare una cache che memorizza questi valori. Un’approssimazione potrebbe essere la seguente:

function fnCache(cache, fn, args) { const key = fn.name + JSON.stringify(args); if (contains(cache, key)) { return get(cache, key); } const result = fn.apply(this, args); set(cache, key, result); return result;}let cache = {};fnCache(cache, findStudent, '03123456J');fnCache(cache, findStudent, '03123456J');

Possiamo eseguire questa funzione quante volte vogliamo che il risultato sia sempre lo stesso. La cosa buona dell’uso di una cache intermedia è che calcoliamo il valore solo una volta, il resto delle volte è ottenuto dalla cache, in questo modo possiamo ridurre i tempi di calcolo o i calcoli che sappiamo richiederanno tempo.

Il problema con questa soluzione è che stiamo mantenendo una cache globale. Siamo un po’ carichi della filosofia di mantenere gli stati il più possibile isolati e può succedere che due funzioni generino due “chiavi” uguali e subiscano un conflitto di risultati.

La soluzione, come vediamo, non è ottimale.

Eliminare la cache globale: la memoizzazione

Invece di fare uso di una memoria così generica, sarebbe molto buono che ogni funzione fosse in grado di gestire la propria cache interna. Alla fine, abbiamo bisogno di un meccanismo che sia trasparente per noi, qualcosa che non ci impedisca di lavorare come prima, qualcosa che ci permetta di dimenticare la gestione della memoria.

Questo è la memoizzazione: La capacità di fare in modo che una funzione pura abbia un meccanismo in cui può ricordare valori già calcolati per risparmiare risorse e tempo. L’idea è quella di avvolgere una funzione in un meccanismo di caching, senza alterare il comportamento di quella funzione.

Una prima proposta potrebbe essere quella di estendere il comportamento di ‘Function’ in questo modo:

Function.prototype.memoized = function () { const key = JSON.stringify(arguments); this._cache = this._cache || {}; this._cache = this._cache || this.apply(this, arguments); return this._cache;}Function.prototype.memoize = function () { const fn = this; if (fn.length !== 1) { return fn; } return function () { return fn.memoized.apply(this, arguments); }}const m_findStudent = findStudent.memoize();

‘memoize’ controlla che la funzione da memorizzare sia unaria e poi restituisce una funzione che farebbe scattare il controllo della cache. ‘memorizzato’ ciò che fa è andare a gestire quella cache interna che abbiamo creato nell’oggetto Function.

Per ora ‘memorizziamo’ le funzioni unarie per rendere la spiegazione più chiara, ma ci sono meccanismi per ‘memorizzare’ qualsiasi tipo di funzione.

Se siete un po’ nervosi per la manipolazione del prototipo di un tipo nativo, abbiamo la stessa soluzione sotto forma di chiusura:

function memoize(fn) { let _cache = {}; if (fn.length !== 1) { return fn; } return function memoized() { const key = JSON.stringify(arguments); _cache = _cache || this.apply(this, arguments); return _cache; }}const m_findStudent = memoize(findStudent);

Mi piace molto di più perché si comporta come il precedente, ma abbiamo il comportamento più disaccoppiato e non manipoliamo il prototipo.

Questo ultimo approccio è molto simile a quello proposto da Rambda con il suo R.memoize, solo che la sua soluzione permette di ‘memorizzare’ funzioni con qualsiasi tipo di arità.

Dimostrare che la memorizzazione funziona

Bene, dati i diversi approcci, sarebbe bello se potessimo dimostrare che la tecnica funziona. Prendiamo un esempio di una funzione pura che può comportare un tempo di calcolo elevato.

Prendiamo una funzione abbastanza semplice che converte una ‘stringa’ con cifratura Caesar:

const getCipherCaesar = s => s.replace(//g, c => String.fromCharCode((c <= 'Z' ? 90 : 122) >= (c = c.charCodeAt(0) + 13) ? c : c - 26))

Non ci interessa l’algoritmo in sé, concentriamoci sulla sua ottimizzazione. Usiamo il metodo di Rambda per ‘memorizzare’:

const m_getCipherCaesar = R.memoize(getCipherCaesar);

Sia ‘m_getCipherCaesar’ che ‘getCipherCaesar’ hanno la stessa firma: data una ‘stringa’, entrambi restituiscono una ‘stringa’ criptata. L’unica cosa che li differenzia è la loro gestione dei risultati.

Per testare questo useremo l’API delle prestazioni come segue:

const start = () => performance.now();const end = (start) => (performance.now() - start).toFixed(3);const test = (fn, arg) => () => fn(arg);

E vedremo come si comporta:

let testCipherCaesar = IO.of(start) .map(R.tap(test(m_getCipherCaesar, 'prueba_memoizacion'))) .map(end);testCipherCaesar.run(); // 0.733 mstestCipherCaesar.run(); // 0.0021 ms

Come possiamo vedere, riduce i tempi di molto.

Dobbiamo essere intelligenti quando “memorizziamo” una funzione. Ci saranno momenti in cui la gestione dei risultati con una cache ha un overhead maggiore della computazione stessa e non ne avremo bisogno. Tuttavia, avremo altri casi in cui possiamo risparmiare molti dati.

Memorizzazione nella ricorsione

La memorizzazione può essere una buona tattica negli algoritmi ricorsivi. La ricorsione si basa sulla rottura di problemi complessi in parti più piccole. Le soluzioni intermedie sono la somma di un insieme che forma la soluzione finale.

La ricorsione tende ad avere un gran numero di risultati intermedi uguali. Se abbiamo detto che la memorizzazione memorizza i risultati in modo che nei prossimi accessi il valore è già calcolato, sembra logico pensare che queste tecniche andranno d’accordo.

Immaginate un caso come il fattoriale. Immaginate che in qualche problema, ho bisogno di conoscere il fattoriale di 100 e il fattoriale di 101. Quando eseguo il fattoriale di 100, logicamente ho bisogno di passare attraverso l’intera ricorsione.

Ma quando improvvisamente ho bisogno del fattoriale di 101. Tutti i fattoriali fino a 100 sono memorizzati nella cache. I tempi di calcolo possono essere drasticamente ridotti. Teniamolo a mente.

Conclusione

Come vediamo un sistema di caching super utile che può farci risparmiare un sacco di tempo inutile. La trasparenza referenziale è un concetto così chiave nella programmazione funzionale che avere così chiari i suoi vantaggi, può aiutarci a trovare le nostre proprie soluzioni.

Addio finale

E questo finisce… volevo ringraziare tutti coloro che hanno contribuito con la loro parte a rendere possibile questa serie. Sono stati mesi in cui ho imparato molto e dove penso di essere migliorato come programmatore. Senza il vostro sostegno e feedback sarebbe stato più difficile trovare il tempo da dedicare a qualcosa come questo.

Volevo ringraziare Luis Atencio per il suo grande libro. Forse uno dei libri che mi hanno aiutato a capire tanti concetti e mi rendono facile ciò che è difficile. Consiglio vivamente il suo libro sulla programmazione funzionale in JavaScript. È un must have.

Leggiamo 🙂

Precedenti post sulla programmazione funzionale in JavaScript:

Introduzione

  1. Programmazione funzionale in JavaScript
  2. Programmazione funzionale in JavaScript: Oggetti
  3. Programmazione funzionale in JavaScript: Le funzioni

Il controllo funzionale del flusso

  1. La programmazione funzionale in JavaScript: Metodi funzionali
  2. Programmazione funzionale in JavaScript: Ricorsione

Modularità funzionale

  1. Programmazione funzionale in JavaScript: Arity e tuple
  2. Programmazione funzionale in JavaScript: Currificazione
  3. Programmazione funzionale in JavaScript: Composizione
  4. Programmazione funzionale in JavaScript: Combinatori

Modelli funzionali

  1. Programmazione funzionale in JavaScript: I funtori
  2. Programmazione funzionale in JavaScript: La monade Maybe
  3. Programmazione funzionale in JavaScript: La monade Either
  4. Programmazione funzionale in JavaScript: La monade IO

L’ottimizzazione funzionale

  1. La programmazione funzionale in JavaScript: Valutazione pigra
  2. Programmazione funzionale in JavaScript: Memorizzazione

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *