Szathmáry László honlapja @ DEIK

functools.lru_cache

Ha egy függvény 1) lassú / költséges, és 2) egymás után többször is meghívjuk ugyanazon paraméterekkel, akkor a függvény által visszaadott értéket érdemes egy cache-ben tárolni. Így az 1. költséges hívás után az összes többi hívás eredménye már a cache-ből fog jönni. (Van még egy feltétel: a függvény legyen tiszta [pure], azaz ugyanazon paraméterekkel meghívva mindig ugyanazt az eredményt adja vissza).

Naiv változat, cache nélkül

from time import sleep

def expensive(n):
sleep(1) # simulate some expensive operations
return n * n

def main():
li = [1, 2, 2, 3, 3, 3, 4, 4, 5]
result = [expensive(n) for n in li]
#
print(li)
print(result)

main()

$ time ./naive.py 
[1, 2, 2, 3, 3, 3, 4, 4, 5]
[1, 4, 4, 9, 9, 9, 16, 16, 25]

real    0m9.058s
user    0m0.047s
sys     0m0.000s

lru_cache használata

A standard könyvtárban van egy függvények cache-elésére szolgáló megoldás, lásd lru_cache. Az LRU cache a least recently used cache rövidítése (mi ez?). Ha telített a cache, akkor egy új elem a legrégebben használt elem helyére fog kerülni.

from functools import lru_cache
from time import sleep

@lru_cache(maxsize=32)
def expensive(n):
sleep(1) # simulate some expensive operations
return n * n

def main():
li = [1, 2, 2, 3, 3, 3, 4, 4, 5]
result = [expensive(n) for n in li]
#
print(li)
print(result)
print(expensive.cache_info())
# expensive.cache_clear() would clear the cache

main()

$ time ./my_lru_cache.py 
[1, 2, 2, 3, 3, 3, 4, 4, 5]
[1, 4, 4, 9, 9, 9, 16, 16, 25]
CacheInfo(hits=4, misses=5, maxsize=32, currsize=5)

real    0m5.054s
user    0m0.040s
sys     0m0.003s

Megadható a cache maximális mérete (maxsize). Ha megadjuk, akkor ennek az értéke legyen 2 egész számú hatványa (hatékonysági okokból). Ha maxsize=None, akkor a cache méretére nincs korlátozás (de ekkor vigyázzunk, nehogy beteljen a memória). Ha nem adjuk meg a cache méretét, akkor az alapértelmezett méret 128 lesz.

Saját cache

Ha egy saját cache-elési megoldást szeretnénk használni, akkor valami ilyesmivel állhatnánk elő:

from time import sleep

cache = {}

def expensive(n):
global cache
if n in cache:
return cache[n]
# else
sleep(1) # simulate some expensive operations
result = n * n
cache[n] = result
return result

def main():
li = [1, 2, 2, 3, 3, 3, 4, 4, 5]
result = [expensive(n) for n in li]
#
print(li)
print(result)

main()

$ time ./my_cache.py 
[1, 2, 2, 3, 3, 3, 4, 4, 5]
[1, 4, 4, 9, 9, 9, 16, 16, 25]

real    0m5.049s
user    0m0.033s
sys     0m0.007s

Ez egy egyszerű megoldás, az lru_cache ennél többet tud (ott pl. korlátozható a cache mérete).

Feladatok

Fibonacci számok. Oldjuk meg előbb cache nélkül, majd teszteljük a futási időt. Hogyan változik a futási idő, ha cache-t is használunk?

Linkek

20170511a