neděle 8. března 2009

Deterministické funkce

Implementoval jsem příklad na kešování argumentů a hodnot deterministických funkcí (jednoho ze zápočtových zadání). Zvolil jsem Python, takže stále existuje prostor pro implementaci zadání v C++ za pomoci šablon (řešení v Pythonu bude jistě mnohem pomalejší). Cílem je zrychlit vyhodnocení některých rekurzivních funkcí.

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é.

@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
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.

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