V následujícím případě je ilustrováno použití na vyhodocení Fibonacciho čísel, při zapamatování si posledních 3 vyhodnocenných hodnot. Rozšíření definice funkce o tuto možnost je při použítí dekorátorů z Pythonu zvášť jednoduché.
Pro vyhodnocení 50. Fibonacciho čísla dojde pouze k 51 volání funkce. Zatímco bez použití dekorátoru jsem čekání na výsledek po několik 10s vzdal. Příklad také ukazuje, že použití správného algoritmu je důležitější než zrychlení dané použitím rychlejšího jazyka.
@deterministic(LRU(3))
def fibonacci(n):
if n >= 2:
return fibonacci(n-1) + fibonacci(n-2)
else:
# F(0) = 0, F(1) = 1
return n
Celá implementace:
class Cache:
'''
Cache interface
'''
def __contains__(self, arg): pass
def __setitem__(self, arg, value): pass
def __getitem__(self, arg): pass
class LRU(Cache):
'''
Implementation of Last Recently Used algorithm.
Only -size- last recently used items are stored in cache
'''
def __init__(self, size):
self._cache = {}
self._order = []
self.size = size
def __contains__(self, arg):
return arg in self._cache
def __setitem__(self, arg, value):
self._order.append(arg)
self._cache[arg] = value
if len(self._cache) > self.size:
i = self._order[0]
del self._order[0]
del self._cache[i]
def __getitem__(self, arg):
self._order.remove(arg)
self._order.append(arg)
return self._cache[arg]
#lambda function which enables adding cache as parameter to
#_deterministic, because
# > @decor(a,b,c)
# > def func(args): pass
#is syntactic sugar for
# > func = decor(a,b,c)(func)
deterministic = lambda cache: lambda f: _deterministic(f, cache)
def _deterministic(f, cache):
'''
decorator which remembers function arguments and returned values
in cache
WARNING: should be used only for function which for the same set of
arguments returns same value.
IMPORTANT: function arguments must be hashable
'''
def df(*args):
if args in cache:
return cache[args]
else:
v = f(*args)
cache[args] = v
return v
return df
@deterministic(LRU(3))
def fibonacci(n):
fibonacci.ncalls += 1
if n >= 2:
return fibonacci(n-1) + fibonacci(n-2)
else:
# F(0) = 0, F(1) = 1
return n
n = 50
fibonacci.ncalls = 0
print 'f(%d): ' % n, fibonacci(n)
print 'number of calls: ',fibonacci.ncalls
Žádné komentáře:
Okomentovat