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 39 |
from time import sleep def power_function_factory(q): """Olyan függvénnyel tér vissza, amely kiszámítja a q hatványát.""" power_values = [] def _power(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 power_values[n] except IndexError: sleep(0.2) # Hosszabb futási idő szimulálása y = q**n power_values.append(y) return y return _power # TESZT # A 2 hatványait visszaadó függvény előállítása. power2 = power_function_factory(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(power2(i), end = ' ') print() # Eredmény: 1 2 4 8 16 32 64 128 256 512 # 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(power2(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.