Home > java > La memoizzazione in Java

La memoizzazione in Java

8 settembre 2010

Translate in English with Google Translate
No, non ho sbagliato a scrivere, volevo proprio dire memoizzazione e non memorizzazione, non mi sono mangiato la “erre”😉

Definizione
La memoizzazione è una tecnica ereditata dai linguaggi funzionali; significa letteralmente “mettere in memoria” e viene utilizzata per conservare in memoria i dati ottenuti da una elaborazione e velocizzare i tempi di risposta in caso di una successiva invocazione. Il termine fu coniato da Donald Michie nel suo articolo “Memo functions and machine learning” (1968) su Nature.

La memorizzazione invece ha un significato più ampio ed utilizza qualunque supporto di memorizzazione e non solo la memoria dell’elaboratore.

La memoria cache è anch’essa una tecnica utilizzata per accellerare i tempi di risposta mantenendo in memoria i dati ma, a differenza della memoizzazione, il risultato dell’elaborazione dipende anche da variabili esterni alla funzione che, subendo delle modifiche, possono cambiare l’output. Questo comporta che i dati presenti nella cache dovranno essere continuamente sincronizzati nel tempo per poter essere aggiornati in base alle modifiche effettuate. Cio’ non avviene nel caso della memoizzazione in quanto l’elaborazione non è condizionata da fattori esterni quindi il dato in memoria resta valido nel tempo e non subisce alcuna modifica.

La tecnica della memoizzazione trova applicazione se vengono rispettate almeno 2 condizioni:

  1. facciamo riferimento a funzioni idempotenti, ossia a funzioni che, a parità di input, ottengono sempre lo stesso risultato indipendentemente da quante volte la funzione viene invocata.
  2. facciamo riferimento a funzioni senza effetti collaterali, ossia a funzioni che utilizzano solo variabili locali e non variabili globali, pertanto  le variabili possono essere modificate solo ed eslusivamente dalla funzione che è stata invocata e nessuna altra funzione puo’ avere accesso a tali variabili.

Quando utilizzarla
Ha senso utilizzarla in 2 ipotesi:

  1. la funzione viene riutilizzata: se si presume che la funzione verrà invocata piu’ volte, altrimenti, se cosi non fosse, memoizzare i dati è completamente inutile in quanto non verranno mai più richiesti e quindi occuperanno inutilmente spazio di memoria.
  2. il dato recuperato è di veloce recupero: se il processo di recupero del dato in memoria richiede molto meno tempo di quello necessario all’elaborazione della funzione, altrimenti il tempo di recupero del dato non giustificherebbe la sua memoizzazione.

Quando non utilizzarla
In base alla prima ipotesi, non ha senso usare questa tecnica se si tratta di:

  • una funzione senza parametri che non verrà mai più invocata: l’output della funzione non verrà mai più utilizzato in quanto la funzione non verrà mai più utilizzata.
  • una funzione con parametri invocata con valori sempre diversi: la funzione richiede necessariamente una nuova elaborazione per poter valutare i diversi valori che vengono passati e per poter determinate l’output.

In base alla seconda ipotesi, non ha senso usare questa tecnica se:

  • il processo di elaborazione richiede un tempo molto basso pertanto non è conveniente mantenere in memoria i dati ma è più semplice effettuare una nuova rielaborazione. In questo caso, se il tempo di processamento è basso, si può risparmiare molto spazio di memoria specialmente nel caso in cui si tratti di una semplice funzione parametrica spesso invocata con valori diversi che occuperebbero molto spazio.
  • il processo di gestione e conservazione del dato in memoria richiede un forte sforzo elaborativo tale che non risulta conveniente tale tecnica. Difatti quando la funzione viene invocata la prima volta, il risultato dell’elaborazione viene memorizzato nella cache. Tale cache è spesso implementata sotto forma di una tabella hash che associa la chiave di invocazione con l’output della funzione.

Funzione senza effetti collaterali
Una funzione produce un effetto collaterale quando modifica un valore o uno stato al di fuori del proprio scoping locale.
In base a questa definzione ci rendiamo conto che al fine dell’applicabilità della tecnica della memoizzazione e affinchè abbia senso mantenere in memoria i dati, occorre essere sicuri che  nessuna altra funzione possa modificare le variabili della nostra funzione.
Difatti a fronte della stessa richiesta, la funzione restituisce sempre la stessa risposta. Questa garanzia ci viene data dal fatto che la funzione  utilizza solo variabili locali e non globali.
L’utilizzo esclusivo di variabili locali garantisce dal fatto che l’elaborazione si basi solo ed esclusivamente:

  • sugli eventuali valori passati ai parametri che vengono passati alla funzione
  • sul valore delle variabili locali della funzione assegnate in sede di elaborazione

Non deve essere consentito a nessuna altra funzione la possibilità di valorizzazione delle variabili utilizzate dalla funzione se non dalla funzione stessa. Se altre funzioni avessero la possibilità di assegnare un valore arbitrario a variabili globale utilizzata dalla funzione, questo influenzerebbe il risultato dell’elaborazione pertanto produrrebbe un risultato arbitrario.
Nello stesso modo in cui nessuna altra funzione possa produrre effetti collaterali, dobbiamo affermare che anche la nostra funzione non deve produrre effetti collaterali. Quindi l’elaborazione della funzione non deve modificare variabili globali, non deve scrivere sul display, modificare il contenuto di files e non deve invocare delle funzioni che a loro volta producano effetti collaterali.

Esempio
Immaginiamo il caso in cui abbiamo una funzione che, a fronte di un input, ci restituire il valore residuo rispetto ad valore massimo.

int max = 5;
public int resto(int x){
   int output = max - x;
   return output;
}

Ogni volta che passiamo il valore 2 alla funzione, verrà effettuata una sottrazione del tipo 5-2=3, pertanto il risultato sarà sempre 3.
Ma cosa succederebbe se una funzione esterna modificasse la variabile max?

public void random(){
    max = (int)(10*Math.random());
}

A fronte dello stesso valore di input, per esempio 2, otterremmo un risultato diverso rispetto ai casi precedenti, ed il risultato potrebbe cambiare se la funzione random() venisse invocata più volte, in quanto inciderebbe sul risultato della nostra elaborzione.
La conclusione mi sembra abbastanza ovvia: non devono essere utilizzati variabili globali altrimenti il risultato potrebbe essere compromesso.

Funzione idempotente
Una funzione è idempotente se non vi è alcuna differenza osservabile fra l’effetto di una singola attivazione della funzione e di N sue attivazioni consecutive effettuate con input identico.
Questa condizione è collegata a quella precedente, ossia alla funzione senza effetti collaterali, ma aggiunge una ulteriore garanzia.
E’ collegata a quella precedente nel senso che, se la nostra funzione fa uso di variabili locali, l’output della funzione non sarà condizionato da altre funzioni, poichè le altre funzioni non possono accedere alle variabili locali della nostra funzione quindi non potranno condizionare l’esito dell’ elaborazione.
Mentre invece l’ulteriore garanzia è data dal fatto che la nostra funzione deve, a fronte dello stesso dato di input, restituire sempre lo stesso output, indipendentemente dal numero di volte in cui viene invocata.
Questo significa che l’algoritmo della nostra funzione deve ottenere un risultato predicibile sulla base dei valori di input, altrimenti ogni volta che la funzione viene invocata potrebbe ottenere un risultato diverso. Questo non vuol dire che la funzione non deve utilizzare al suo interno dei valori random, ma sicuramente l’output della funzione non deve essere compromessa da tali valori.

Utilizzo della memoizzazione
Iniziamo subito col dire che tale tecnica si utilizza per le funzioni e non per le procedure, pertanto in java cio’ significa che non verrà utilizzata per i metodi void ma solo per i metodi che restituiscono un tipo. Perchè? Perchè l’unico motivo per cui si invocano metodi void è per il side-effect ossia per apportare azioni su variabili globali, log dell’applicazione ed altro. Che motivo avrebbe eseguire l’algoritmo di una funzione senza ottenere nessun effetto?  Nessuno. Quindi ci concentriamo solo sulle funzioni idempotenti e senza side-effect e non sulle procedure.

Per semplicità possiamo dividere l’esecuzione di una funzione in 3 momenti:

  1. recupero dei valori di input
  2. esecuzione dell’algoritmo
  3. restituzione del valore di output

Vediamo di seguito come implementare la memoizzazione nel caso in cui si utilizzi una chiave semplice o composta. La chiave viene generata partendo dai parametri della funzione pertanto sarà nostro compito nostro quello di decidere come create l’oggetto che rappresenta la nostra Chiave semplice o composta.

Chiave semplice
Facciamo l’esempio di una funzione che calcola il quadrato di un numero passato in input.
La funzione potenza() è invocata passando 1 parametro che viene utilizzato per effettuare una elevazione a potenza. Tale funzione restituisce, a parità di input, sempre lo stesso output quindi è ideomatica. Inoltre non utilizza nessuna variabile globale, non viene invocata la stampa su display o su files, non viene invocata nessuna altra funzione che abbia side-effect pertanto possiamo affermare che è senza effetti collaterali.
Questo ci assicura che le 2 condizioni necessarie sono state rispettate.

    public int potenza(int x) {
        int output = x * x;
        return output;
    }

Vediamo allora come memoizzare il risultato dell’elaborazione.
Decidiamo di creare una tabella di hash con coppie chiave-valore in cui viene memorizzata:

  • come chiave: il valore di input passato alla funzione
  • come valore: il risultato di output della nostra elaborazione
private static Hashtable <Integer, Integer>  cache = new Hashtable <Integer, Integer>();

    public int potenza(int x) {
        int output = 0;
        if (cache.containsKey(x)) {
            output = cache.get(x);
        } else {
            output = x * x;
            cache.put(x, output);
        }
        return output;
    }

Ipotizziamo che la funzione potenza() venga invocata 2 volte ed in entrambi i casi venga passato lo stesso valore.

  • La prima volta che la funzione potenza() viene invocata:viene cercata nella tabella hash la chiave, cioè il valore passato al metodo, che poichè non verrà trovata si procederà all’elaborazione dell’algoritmo e dopodichè si inserirà nella tabella di hash la coppia chiave-valore per essere disponibile per la prossima invocazione.
  • La seconda volta che la funzione potenza() viene invocata: viene cercata nella tabella hash la chiave, che poichè è presente, viene restituito il corrispettivo valore dell’output.

Chiave composta
Esaminiamo adesso il caso in cui la funzione presenta più parametri. Il caso di una semplice somma algebrica:

    public int somma(int x, int y) {
        int output = x + y;
        return output;
    }

In questo caso la chiave del metodo è composta. Questo deve essere gestito nella cache che gestisce la memoizzazione.
Per fare questo ho creato un javabean dal nome Chiave che utilizzo come chiave nella tabella hash ed inoltre ho sovrascritto i metodi hashcode() ed equal() per gestire in modo opportuno la chiave.

public class Chiave {

    private int x;
    private int y;

    public Chiave(int x, int y){
        this.x = x;
        this.y = y;
    }

    public int hashCode(){
        return x;
    }

    public boolean equals(Object c) {
        boolean equal = false;
        if (c instanceof Chiave && ((Chiave)c).x == this.x && ((Chiave)c).y == this.y )
            equal = true;
        return equal;
    }

}

A questo punto modifichiamo la funzione somma() in modo da gestire la memoizzazione della funzione ed il gioco è fatto:

private static Hashtable <Chiave, Integer> cacheComposta = new Hashtable <Chiave, Integer>();

    public int somma(int x, int y) {
        int output = 0;
        Chiave chiave = new Chiave(x,y);
        if (cacheComposta.containsKey( chiave )) {
            output = cacheComposta.get( chiave );
        } else {
            output = x + y;
            cacheComposta.put(chiave, output);
        }
        return output;
    }

Numero di Fibonacci
La memoizzazione permette di ottenere dei notevoli miglioramenti delle performance tanto maggiori quanto oneroso o frequente è l’elaborazione dell’algoritmo della funzione.
Un caso che trova subito applicazione è quando si abbia a che fare con funzioni ricorsive le quali, per loro natura, possono gravare anche pesantemente sul processore. In questo esempio prenderemo in considerazione il numero di Fibonacci che rappresenta un caso di ricorsione multipla. In un mio precedente articolo faccio riferimento alla tecnica della ricorsione ed al numero di Fibonacci.
Il numero di Fibonacci può essere sintetizzato in una funzione java di questo tipo:

public int fibonacci(int n) {
  if (n < 2)
    return n;
  else
    return fibonacci(n-2) + fibonacci(n-1);
}

Come applicare la memoizzazione alla ricorsione?
Così come nei casi precedenti ci dobbiamo assicurare che la funzione sia idempotente e senza side-effect successivamente creiamo una cache dei dati da memoizzare.
In questo caso le prime 2 condizioni sono rispettate, quindi modifichiamo la funzione per creare ed associare alla cache le chiavi.
Abbiamo quanto segue:

private static Hashtable<Integer, Integer> cache = new Hashtable<Integer, Integer>();

    public int fibonacci(int n) {
        if (n < 2)
            return n;
        else if (!cache.containsKey(n))
            cache.put(n, fibonacci(n - 2) + fibonacci(n - 1));
        return cache.get(n);
    }

Dalle prove effettuate si evidenzia un netto miglioramento delle prestazioni nel caso in cui si utilizza la tecnica della memoizzazione nel numero di Fibonacci.

Di seguito mostro le tabelle di confronto dei 2 casi, con e senza la memoizzazione di numeri di Fibonacci da 40 a 48.
E’ evidente il miglioramento delle prestazione nel caso della memoizzazione rispetto al caso di un suo non utilizzo.

Link utili 
Wikipedia Definizione Idempotenti : http://it.wikipedia.org/wiki/Idempotenza

Wikipedia Definizione Numero di Fibonacci: http://it.wikipedia.org/wiki/Numero_di_Fibonacci

Memoization : http://www.codedanger.com/caglar/?p=104

OnJava: http://www.onjava.com/pub/a/onjava/2003/08/20/memoization.html
Categorie:java
  1. Non c'è ancora nessun commento.
  1. 9 maggio 2013 alle 5:57 PM
I commenti sono chiusi.
%d blogger cliccano Mi Piace per questo: