Számos kiváló cikk szól a memoizációnak nevezett optimalizálási technikáról. Itt és itt érheted el őket. Mi most egy rövid áttekintést adunk arról, hogy mi is az a memoizáció. Kicsit továbbmegyünk, és lépésről lépésre elemezzük, hogy a “memoizáló “kód valójában mit is csinál, soronként. A cikk végére teljesen meg fogja érteni a memoizációt.

A memoizálás a hosszú rekurzív/iteratív függvények gyorsabb futtatásának programozási gyakorlata.

Hogyan, kérdezi? Azáltal, hogy gyorsítótárba helyezzük azokat az értékeket, amelyeket a függvény a kezdeti végrehajtás után visszaad.

Amikor ugyanazt az értéket adjuk be a memoizált függvényünkbe, az a függvény újbóli futtatása helyett a gyorsítótárban tárolt értéket adja vissza, így növelve a teljesítményt. Többé nem kell a programunknak minden egyes számot újraszámolnia, hogy megkapja az eredményt.

Félelmetesen hangzik, igaz? Nos, ami még jobb, hogy nem nehéz megérteni, mit csinál egy memoize függvény, ha egyszer lebontjuk a kódot.

Itt egy példa egy alapvető memo függvényre:

Kezdjük az elejéről…

Az úgynevezett anonymous closure-t adjuk vissza. A névtelen zárlatunk képes örökölni bármilyen változót vagy ebben az esetben függvényt, amelyet a memo-be adunk át. Ezután játszhatunk az argumentumobjektummal, amit az átadott függvényünk biztosít.

Side Note: Tehát, ha minden függvénynek van argumentumobjektuma, akkor miért nem örökljük az memo argumentumobjektumát? Azért, mert a lezárások általában nem öröklik egy külső függvény argumentumobjektumát. Ezt a szabályt használjuk ki a magunk javára, hogy eljátszhassunk a memoizálni kívánt függvénnyel.

Lássuk, hogy pontosan mit is csinál a memoizálás egy nagyon egyszerű és nem praktikus példán keresztül. Egyébként érdemes bemásolni/beilleszteni ezt a kódot, vagy bármilyen más kódot, hogy igazán ráérezzünk a működésére.

Azt hiszem, értjük a lényegét ennek a kódpéldának. Gyakorlatilag magáért beszél. Bontsuk ki egy kicsit jobban, megnézve egy pillanatképet a valódi memo függvényünkről:

Most, hogy lebontottuk, mit csinál egy memo függvény, hozzunk létre egy függvénykifejezést, és adjunk át egy rekurzív Fibonacci függvényt a memo be, és nézzük meg, mi történik.

//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}
*/

Következtetés

A memoizálás demisztifikálttá válik, ha kulcs-érték párokra vezetjük le. Mindössze annyit teszünk, hogy létrehozunk egy objektumot, ellenőrizzük a meglévő értékeket, amelyek megfelelnek a felhasználói bemenetnek, és új kulcs-érték párokat tárolunk, ha azok nem léteznek az objektumunkban.

Az összes adat tárolása természetesen azt jelenti, hogy memóriát fogunk használni. A legjobb, ha a memoizációt olyan függvényeken valósítjuk meg, amelyek tiszták és nehéz, ismétlődő számításokat tartalmaznak.

Bónusz:

A szórakozás kedvéért itt van a memoizátorunk egy funkcionális változata:

.