Memoization

Memoization is een methode in het programmeren die gebruikt wordt om een functie te optimaliseren. Memoization is een vorm van caching en is verwant aan dynamisch programmeren.

Bij memoization slaat een functie de waarde die hij voor de gegeven argumenten berekend heeft op. Als de functie opnieuw wordt aangeroepen met dezelfde argumenten hoeft het resultaat niet opnieuw berekend te worden, maar kan direct geretourneerd worden.

Voorbeeld: de Fibonacci-reeks

De onderstaande C-functie berekent het nde Fibonaccigetal (zonder memoization):

int fib(int n) {
        if (n < 1) return 0;
        if (n == 1) return 1;
        return fib(n-1) + fib(n-2);
}

Wanneer we gebruikmaken van memoization kan de functie er zo uitzien:

int fib2(int n) {
 
        static int r[10000];
        int t;
        
        if (n < 1) return 0;
        if (r[n]) return r[n];
        if (n == 1) 
                t = 1;
        else
                t = fib2(n-1) + fib2(n-2);
        return r[n] = t;
}

Voor het berekenen van het 10e, 20e en 40e fibonaccigetal wordt de eerste functie respectievelijk 176, 21.890 en 331.160.280 keer recursief aangeroepen. De tweede, gememoizeerde, functie heeft slechts respectievelijk 18, 38 en 78 recursieve aanroepen nodig. Door het toepassen van memoization is de looptijd van de functie teruggebracht van exponentieel ($O(x^{n})$) tot lineair ($O(n)$).