Memoization

Supponiamo di avere un metodo che dobbiamo chiamare più volte e che esegue un calcolo lungo o comunque dispendioso in termini di risorse.

Supponiamo anche che non sappiamo prevedere con che parametri chiameremo questo metodo e quindi capiterà di chiamarlo più volte bella stessa esecuzione con gli stessi parametri e ripetere lo stesso calcolo più volte.

Come si ottimizza uno scenario del genere? Una strategia molto semplice è quella di utilizzare una cache per recuperare il valore se già stato calcolato. Un esempio potrebbe essere il seguente:

private static Dictionary<int, long> Memoized = new Dictionary<int, long>();

public static long Fibonacci(int n)
{
    if (n == 1 || n == 2)
        return 1;

    long r;

    if (Memoized.TryGetValue(n, out r))
        return r;

    r = Fibonacci(n - 1) + Fibonacci(n - 2);

    Memoized.Add(n, r);

    return r;
}

static void Main(string[] args)
{
    System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();

    sw.Start();

    var fib = Fibonacci(25);

    sw.Stop();
    var el1 = sw.ElapsedMilliseconds;

    sw.Restart();

    var fib2 = Fibonacci(26);


    sw.Stop();
    var el2 = sw.ElapsedMilliseconds;


}

Nel codice di esempio abbiamo ottimizzato la funzione di Fibonacci utilizzando in modo esplicito la sua definizione, non abbiamo solamente salvato i valori già calcolati per non ricalcolarli abbiamo anche sfruttato il fatto che i valori di n dipendono dai precedenti anch’essi già inseriti in cache.

In generale non è possibile effettuare un’operazione del genere, non tutte le funzioni sono ricorsive e anche le funzioni ricorsive hanno diverse regole di ricorsione che è difficile generalizzare.

Con l'utilizzo dei generics di C# è possibile creare una classe che ci permette di applicare questa tecnica ad una funzione qualunque.

public class Memoize<TIn, TOut>
{
    Dictionary<TIn, TOut> Memoized = new Dictionary<TIn, TOut>();
    Func<TIn, TOut> Function;

    public Memoize(Func<TIn, TOut> function)
    {
        Function = function;
    }

    public TOut GetValue(TIn input)
    {
        TOut r;

        if (Memoized.TryGetValue(input, out r))
            return r;

        r = Function(input);

        Memoized.Add(input, r);

        return r;
    }

}


static void Main(string[] args)
{
    var memFib = new Memoize<int, long>(Fib);

    System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();

    sw.Start();

    var fib1 = memFib.GetValue(25);

    sw.Stop();

    var el1 = sw.ElapsedMilliseconds;

    sw.Restart();

    var fib2 = memFib.GetValue(25);

    sw.Stop();

    var el2 = sw.ElapsedMilliseconds;
}

In questo esempio abbiamo ridefinito la funzione di Fibonacci nel modo classico e poi abbiamo utilizzato la funzione Memoize per ottimizzarla. In questo caso il test per avere senso deve essere effettuato sullo stesso valore in quanto non stiamo sfruttando la struttura ricorsiva della funzione. È evidente che questa classe può funzionare solo per funzioni di una variabile ma è semplice generalizzare l’approccio.

Pubblicato il 02 set 2016

0 commenti