Tegyük fel, hogy olyan műveletet kell végezni a programunknak, amely érzékelhető futási idő növekedéssel jár, és ráadásul ezt többször is végre kell hajtani. Ha ez a művelet determinisztikus, vagyis ugyanarra a bemenő adatra vagy kérésre mindig ugyanazt a kimenő adatot, illetve választ adja, akkor alkalmazhatjuk az úgynevezett memoizációt. Ez lényegét tekintve azt jelenti, hogy adott kérésekre egyszer már meghatározott eredményeket eltároljuk a memóriában, és egy újabb kérés esetén nem a jelentős futási idejű műveletet hatjuk végre megint, hanem egyszerűen a memóriában tárolt megfelelő értéket adjuk vissza.
A memoizáció tehát lényegében az időfelhasználást konvertálja memóriafelhasználássá.
Ez a technika annál nagyobb futási idő megtakarítást eredményez (és annál kevesebb többlet memóriafelhasználást igényel), minél gyakrabban kell ugyanazon bemenetre a válaszokat megkapni.
A memoizációt több módon is meg lehet valósítani. Az egyik gyakori mód a closure alkalmazása. Ennek bemutatását látjuk az alábbi példaprogramban.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
from time import sleep def hatványfüggvénygyártó(q): hatványértékek = [] def _hatvány(n:int): # Ha az n értékhez tartozó érték el van tárolva már, akkor azzal térünk vissza. # Ha nincs, vagyis a tárolást végző lista n indexű eleme még nem létezik, akkor # kiszámoljuk a hatványértéket, eltároljuk és aztán visszatérünk ezzel az értékkel. try: return hatványértékek[n] except IndexError: sleep(0.2) # Hosszabb futási idő szimulálása y = q**n hatványértékek.append(y) return y return _hatvány # TESZT # A 2 hatványait visszaadó függvény előállítása. hatvány2 = hatványfüggvénygyártó(2) # Ha először kérjük ki egy adott indexhez tartozó hatványértéket, akkor érezhető idő kell a kiszámolásukhoz. for i in range(10): print(hatvány2(i), end = ' ') # Eredmény: 1 2 4 8 16 32 64 128 256 512 print() # Ha viszont később ugyanazon indexekhez bármikor újra kikérjük a hatványértéket, akkor azokat szinte azonnal megkapjuk. # Az eddig még nem számolt értékek meghatározásához természetesen most is idő kell, de utána már később ezeket is gyorsan fogjuk megkapni. for i in range(11): print(hatvány2(i), end = ' ') # Eredmény: 1 2 4 8 16 32 64 128 256 512 1024 |
Az egyszerűség és áttekinthetőség kedvéért a bemutatott closure függvény adott egész szám hatványát számoló függvényt jelent, ahol a hatványalapot a körülzáró függvény q argumentumával határozzuk meg a meghívásakor. A hatványszámolás nem lassú, ezért ahhoz, hogy egy érzékelhető futási idő növekményt érjünk el, azt a szabványos könyvtár time moduljának sleep() függvényével szimuláljuk, aminek argumentumaként másodpercben mérve kell megadni a késleltetési időt.
A hatványértékeket a körülzáró függvény lokális változójával hivatkozott list típusú sorozatban tároljuk. Mint tudjuk (lásd egy korábbi bejegyzésben is) a closure függvény e lokális változó értékéhez bárhol a programban a hívása helyén is hozzá tud férni. Ha még nincs az adott egész számhoz eltárolt hatványértéke, akkor azt kiszámolja, és ebben a listába eltárolja. Ha pedig az adott indexhez van már tárolt érték, akkor azzal tér vissza.
Ez a példa csak az elvet hivatott bemutatni. A memoizálással és annak megvalósításával kapcsolatban még merülnek fel részletkérdések. Ezekkel mélyebben a Python tudásépítés lépésről lépésre című e-könyv „Tár-idő csereügylet – memoizálás a futási idő csökkentésére”, valamint a „Memoizálás támogatása” fejezetek foglalkoznak.