Function Caching via Memoization

To explain memoization, see these different versions of Fibonacci:

Purely recursive. Highly inefficient. Recalculates every value for every calculation.

Iterative. Much faster.

Here is the memoization technique. A 'cache' dictionary of { (args) : (return_val), } is created. This allows us to quickly locate and reuse any value that has already been calculated.

	fib_vals = {1:1, 2:1}
	def fib(n):
	if n <= 2:
	return 1
	if n in fib_vals:
	return fib_vals[n]
	else:
	fib_vals[n] = fib(n - 1) + fib(n - 2)
	return fib_vals[n]

view raw fibo_memo_basic.py hosted with ❤ by GitHub

Here is the same memoization design, implemented as a decorator.

	def memoize(func):
	"""Decorator for memoization via 'cache' dictionary."""
	cache = {}
	def memoed_func(*args):
	if args not in cache:
	cache[args] = func(*args)
	return cache[args]
	memoed_func.cache = cache
	return memoed_func
	@memoize
	def fib(n):
	"""Demos use of memoization decorator. """
	if n <= 2:
	return 1
	else:
	return fib(n-1) + fib(n-2)

view raw memo_decorator.py hosted with ❤ by GitHub