Rekurzió és memoization – a cache-elés művészete

fibonacci rekurzió memoization

Kinek szól ez a cikk

Ez a cikk azoknak szól, akik tudják mi az a rekurzió, és valamilyen szinten használták is a programozói gyakorlatban. Amennyiben nem tudod, mi az a rekurzió, először kattints erre a cikkünkre.

Az óráimon többször előfordult, hogy a felvett tanórák, az ingyenes YouTube videókurzusunk, a zárt GitHub-anyagok és a személyes konzultációs lehetőségek ellenére a hallgatók a rekurzió – és főleg a memoization – témakörében extra támogatást kértek. Nem csoda, hiszen a rekurzió kezdő programozók számára önmagában egy nehezen emészthető témakör a ciklusokhoz képest, viszont fontos, mert a gyakorlati életben vannak helyzetek, amikor rekurzióval könnyen meg lehet oldani egy olyan problémát, ami ciklussal vagy egyéb nyelvi eszközzel körülményes lenne.

A memoization röviden

A programozás egyik izgalmas és hasznos technikája a memoization (azaz cache-elés, gyorsítótárazás), amely segít abban, hogy hatékonyabbá tegyük a rekurzív algoritmusunkat. Kezdőként érdemes megismerkedni ezzel a módszerrel, mert nemcsak a Java-ban, hanem más programozási nyelvekben is könnyen alkalmazható. Ezen cikk során lépésről lépésre megmutatjuk, hogyan működik a memoization és hogyan tudod felhasználni Java-ban, hogy gyorsítsd az algoritmusokat és optimalizáld a futási teljesítményt.

A memoization lényege, hogy a számítás eredményét elmentjük, és ha később újra szükség van rá, akkor nem számítjuk ki újra, hanem az elmentett értéket használjuk. Ez különösen hasznos olyan rekurzív függvényeknél, amelyek ugyanazt az értéket többször is kiszámítják.

Itt felmerül az a kérdés, hogy milyen típusú rekurzív hívásoknál számoljuk ki ugyanazt az eredményt többször (sokszor anélkül, hogy ezt észrevennénk). Mire a cikk végére érsz, nem csak választ kapsz a kérdésedre, hanem megnézünk egy olyan módszert, amit nyelvfüggetlenül használhatsz: ez a memoization módszere.

A Fibonacci-sor

Ha olvastál már rekurzióról, a Fibonacci-sorral, mint rekurzió alappéldájával valószínűleg találkoztál. A Fibonacci-sor egy olyan számokból álló sor, amelynek az első két eleme adott (legyen ez most 0 és 1), és minden ezt követő elem az azt megelőző két elem összegeként állítható elő. Rövidebben leírva tehát:

F0 = 0
F1 = 1
Fn = Fn-1+Fn-2 (n>1 esetére)

Ez alapján tehát a Fibonacci-sorunk első néhány eleme így fest: 0, 1, 1, 2, 3, 5, 8, 13, 21, …

Legyen most az a feladatunk, hogy metódust kell írni, ami bevesz egy paramétert (legyen ez n), és visszaadja a Fibonacci-sor n-edik elemét. Egy ilyen metódus megírásánál a rekurzió kiváló eszköz, mivel a sor definíciójában leírtak alapján az F0 és az F1 eset lesznek az úgynevezett base case, az Fn eset pedig lesz maga a rekurzív hívás, ahol a sor korábbi elemei alapján számoljuk ki a következő elemeket. Elsőre konfúz lehet, de kellő gyakorlattal ez a metódus néhány pillanat megírható, és hasonlóképpen fog kinézni:

public static long fibonacci(int n) {
if (n == 0) {
return 0; //base case --> minden rekurzív függvény esetén legyen base case-ed
}
if (n == 1) {
return 1; //base case --> minden rekurzív függvény esetén legyen base case-ed
}
return fibonacci(n - 1) + fibonacci(n - 2); //rekurzív hívás
}

A naiv implementáció problémája

A fent található naiv Fibonacci-implementáció elvégzi a kívánt feladatot, viszont van egy pár szempont, aminek tekintetében szuboptimálisan működik.

Egyrészt a Fibonacci-sor egyes elemei rendkívül gyorsan nőnek, éppen ezért a long változótípus már a 100. érték meghatározására sem lesz megfelelő, de ettől most tekintsünk el. Ilyen esetekre van egyébként a BigInteger osztály, amely szinte a végtelenségig képes számokat kezelni. Amennyiben szeretnél gyakorolni, mindenképp javaslom, hogy írd át a fenti metódust úgy, hogy BigInteger-rel térjen vissza, és sokkal nagyobb számokat is megfelelően tudjon megjeleníteni, mert ez remek gyakorlási lehetőség

A probléma, amivel viszont részletesen szeretnénk foglalkozni, hogy bármilyen meglepő is, ez az algoritmus lassú. Próbáljuk ki, hogy a main-ben meghívjuk ezt a metódust, és nézzük meg, mi történik:

public static void main(String[] args) {
for(int i = 0; i < 50; i++){
System.out.println(fibonacci(i));
}
}

Csak a 49. elemig írattuk ki a Fibonacci-sor aktuális elemeit, viszont már így is iszonyú lassú. Továbbá érdekesség az is, hogy az első elemeket eszméletlenül gyorsan kiszámolja az algoritmusunk, és csak a végén lassul le nagyon.

Miért lassú az algoritmusunk?

A rövid válasz az, hogy azért, mert úgy írtuk meg, hogy lassú legyen 🙂 A probléma mindenképp a rekurzív hívásban keresendő, azaz ebben a sorban:

return fibonacci(n – 1) + fibonacci(n – 2);

Ez a sor az, ami eszméletlenül lassúvá, (egészen pontosan 2n időbeli komplexitásúvá) teszi az algoritmusunkat. Na de mit csinál pontosan a fenti kódsor? A lenti kép tökéletesen bemutatja azt, hogy mi történik. A fibonacci(10) az algoritmus szerint például a fibonacci(9) + fibonacci(8) hívás eredményeként jön létre, de a fibonacci(9)-hez úgy jutunk hozzá, ha a fibonacci(8) + fibonacci(7) összeget meghatározzuk. A fibonacci(8)-hoz és a fibonacci(7)-hez viszont megint két értéket kiszámol az algoritmusunk, és így tovább.

fibonacci(10)
/ \
fibonacci(9) fibonacci(8)
/ \ / \
fibonacci(8) fibonacci(7) fibonacci(7) fibonacci(6)
/ \ / \ / \ / \

fibonacci(7) fibonacci(6) fibonacci(6) fibonacci(5) fibonacci(6) fibonacci(5) fibonacci(5) fibonacci(4)

… … … … … … … … … … és így tovább

Mi a fő probléma tehát? A fő probléma az, hogy a már előzetesen kiszámolt eredményeket újra és újra kiszámoljuk, ezért egy hatalmas fa jön létre, ahol minden egyes csúcs egy-egy számítás, és látjuk, hogy a fibonacci(2) hívás például a jó ég tudja, hányszor történik meg – és ez eszméletlenül komoly számítási kapacitást jelent, ahogy fent láttuk, már 50 elem kiszámolása esetén is.

Mi a megoldás?

A megoldás az így létrejött fa ,,lecsonkítása”, így O(2n)-ről O(n)-re csökken az algoritmusunk időbeli komplexitása.

Hogyan tudjuk ezt elérni? Úgy, hogy a már kiszámított értékeket tároljuk egy a Java által biztosított struktúrában. Ez lehet tömb is, én most a Map interfész egy implementációját választom. Ha nem ismered a Map-et, javaslom ingyenes YouTube-videósorozatunknak ezt és az ezt követő videóját megtekintésre:

Mindenesetre a Map interfész és a legegyszerűbb és leggyakoribb Map-implementáció, a HashMap segítségével így néz ki a megoldásunk:

import java.util.HashMap;
import java.util.Map;

public class Main {

private static Map<Integer, Long> memo = new HashMap<>();

public static long fibonacci(int n) {
if (n <= 1) {
return n;
}
if (memo.containsKey(n)) {
return memo.get(n);
}

long result = fibonacci(n - 1) + fibonacci(n - 2);
memo.put(n, result);

return result;
}
}

Mit is csinál ez a kódrészlet? Gyakorlatilag ugyanazt, mint az előző, annyi különbséggel, hogy:

  • mielőtt kiszámolnánk az eredményt, megnézzük, hogy a cache-ünk tartalmazza-e azt (ez a memo.containsKey…-es sorunk). Amennyiben tartalmazza, kivesszük onnan az eredményt visszatérünk az adott értékkel, és a fának azt a részét már le is vágtuk 🙂
  • amennyiben nem tartalmazza, kiszámoljuk, és az aktuálisan kiszámolt eredményeket azon nyomban betesszük a cache-ünkbe (ez a memo.put… kezdetű sorunk)
  • lényegében annyit csinálunk, hogy a rekurzív hívás előtt megnézzük, hogy az adott eredmény kiszámolásra került-e már, és ha igen, csak kivesszük az értéket a cache-ünkből

Csodálatos, ugye?

Mennyit gyorsult az algoritmusunk?

Eszméletlenül sokat. Már 100 elemszám esetén is azt jelenti, hogy 2100 nagyságrendű művelet helyett 100-zal korrelálót végeztünk el. Ezért van az, hogy 50 elemszám esetén is lassú volt az előző algoritmusunk. No de teszteljük az újonnan megírt memoization algoritmusunkat:

import java.util.HashMap;
import java.util.Map;

public class Main {

private static Map<Integer, Long> memo = new HashMap<>();

public static void main(String[] args) {
for(int i = 0; i < 50; i++) {
System.out.println(fibonacci(i));
}
}


public static long fibonacci(int n) {
if (n <= 1) {
return n;
}
if (memo.containsKey(n)) {
return memo.get(n);
}

long result = fibonacci(n - 1) + fibonacci(n - 2);
memo.put(n, result);

return result;
}
}

Egy pillanat alatt lefut. És ha az 50-et átírom 500-ra vagy 50000-re, akkor is. Más kérdés, hogy ezekre a számokra már BigInteger-t kéne használnom, de challenged accepted – várjuk az info@ak-akademia.hu e-mail címre a BigInteger-rel megoldott memoization-algoritmusokat!

A memoization limitációi

Sajnos a memoization sem fenékig tejfel és megvannak a saját limitációi, határai. Azt megbeszéltük, hogy time complexity (időbeli komplexitás) tekintetében a memoization hatalmas sebességnövekedést hozott a Fibonacci-sorunk n-edik elemének a kiszámítása esetén, de költséget is fizettünk. Mi ez a költség?

A költség a space complexity. Magyarul lefordítva ez nagyjából annyit jelent, hogy n művelet elvégzése esetén (tehát itt pl. fibonacci(n) kiszámítása esetén) hány egységnyi memóriát foglalunk el. Ez ebben az esetben n, mivel végső soron a Fibonacci-sorunk minden egyes elemét tárolni fogjuk az első kettőt kivéve. Az naiv implementációban ez 0 db művelet volt.

Végszó

A lenti táblázatban láthatod a naiv implementáció és a memoization-nel felturbózott algoritmusunk összehasonlítását:

Naiv implementációMemoization
Time complexityO(2n) – borzasztóan lassúO(n) – gyors
Space complexityO(1) – semennyi memóriát nem foglalO(n) – nem foglal sok memóriát, de bizonyos esetekben probléma lehet

Ez a gyakorlatban azt jelenti, hogy még úgy is, hogy időben rengeteget takarítunk meg, bizonyos esetekben, amikor kevés memória áll rendelkezésre (például beágyazott rendszereknél) érdemes a kapacitásbeli limiteket figyelembe véve optimalizálni az algoritmusunkat.

Szerző: Nagy Csongor