Der findes flere fremragende artikler om den optimeringsteknik, der kaldes memoization. Du kan få adgang til dem her og her. Det, vi vil gøre, er at give dig et kort overblik over, hvad memoization er. Vi vil gå lidt videre ved at foretage en trinvis analyse af, hvad “memoizing”-kode faktisk gør, linje for linje. Ved slutningen af artiklen vil du fuldt ud forstå memoisering.

Memoisering er den programmatiske praksis, der går ud på at få lange rekursive/iterative funktioner til at køre meget hurtigere.

Hvordan, spørger du? Ved at cache de værdier, som funktionen returnerer efter den første udførelse.

Når vi indtaster den samme værdi i vores memoiserede funktion, returnerer den den værdi, der er gemt i cachen, i stedet for at køre funktionen igen, hvilket øger ydelsen. Dit program behøver ikke længere at genberegne hvert tal for at få et resultat.

Det lyder fantastisk, ikke? Nå, men hvad der er endnu bedre er, at det ikke er svært at forstå, hvad en memoize-funktion gør, når først du bryder koden ned.

Her er et eksempel på en grundlæggende memo funktion:

Lad os starte fra begyndelsen…

Vi returnerer det, der kaldes en anonymous closure. Vores anonyme closure er i stand til at arve enhver variabel eller, i dette tilfælde, funktion, der er overgivet til memo. Vi kan derefter lege med det arguments-objekt, som vores indleverede funktion giver os.

Sidebemærkning: Så hvis alle funktioner har et arguments-objekt, hvorfor arver vi så ikke arguments-objektet i memo? Det skyldes, at lukninger som regel ikke arver en ydre funktions arguments-objekt. Vi bruger denne regel til vores fordel for at lege med den funktion, vi ønsker at memoisere.

Lad os nedbryde præcis, hvad memoisering gør, ved at se på et meget simpelt og upraktisk eksempel. I øvrigt bør du kopiere/indsætte denne kode, eller enhver kode for den sags skyld, for virkelig at få en fornemmelse af, hvordan det fungerer.

Jeg tror, vi har forstået essensen af dette kodeeksempel. Det taler praktisk talt for sig selv. Lad os konkretisere det lidt mere ved at se på et øjebliksbillede af vores rigtige memofunktion:

Nu da vi har nedbrudt, hvad en memofunktion gør, lad os oprette et funktionsudtryk og sende en rekursiv Fibonacci-funktion ind i memo og se, hvad der sker.

//Now we'll test our code!
// =======TEST=======
fib(10)//On the first try we need to load//=> loading…//=> loading…//=> loading…//=> loading…//=> loading…//=> 4 loadings later we get...//=> 89// And on the second try…fib(10)//=> 89//No loading! Yaay!//The cool thing about memoizing the recursive Fibonacci algorithm is that once we make a call for the value of the nth number in the series, we are able to store all the previous numbers in the series.//So if we try...
fib(7) //=> 21
//We don't have to recalculate anything.//And if we want to try fib(11)...
fib(11)
//loading...
//=> 144
//Our memoized recursive function already cached fib(1-10),so all it needed to do was to calculate the cached values. // This is what the cache now looks like:
/*
{ '{"0":0}': 1,
'{"0":1}': 1,
'{"0":2}': 2,
'{"0":3}': 3,
'{"0":4}': 5,
'{"0":5}': 8,
'{"0":6}': 13,
'{"0":7}': 21,
'{"0":8}': 34,
'{"0":9}': 55,
'{"0":10}': 89,
'{"0":11}': 144}
*/

Slutning

Memofunktionen bliver afmystificeret, når man koger den ned til nøgle-værdipar. Det eneste, vi gør, er at oprette et objekt, kontrollere, om der findes værdier, der matcher brugerens input, og lagre nye nøgle-værdipar, hvis de ikke findes i vores objekt.

Lageringen af alle disse data betyder naturligvis, at vi bruger hukommelse. Det er bedst at implementere memoisering på funktioner, der er rene og involverer tunge, gentagne beregninger.

Bonus:

Just for sjov, her er en funktionel version af vores memoisering: