#!/usr/bin/env python
# -*- coding: iso-8859-1 -*-

# Dinko Korunic 'kreator', 2006.
# memoize decorator example
# TODO: flatten keyword dicts using cPickle.dumps() and hash..

import timeit

def memoize(func):
	memoize_cache = {}
	def memoized_func(*args):
		#print "memoizing %s.%s" % (func.__module__, func.__name__)
		if args in memoize_cache:
			return memoize_cache[args]
		else:
			result = func(*args)
			memoize_cache[args] = result
			return result
	memoized_func.__name__ = func.__name__
	memoized_func.__doc__ = func.__doc__
	memoized_func.__dict__ = func.__dict__
	return memoized_func

@memoize
def fibm(n):
	if (n < 2):
		return n
	else:
		return fibm(n - 1) + fibm(n - 2)

def fibd(n):
	if  2 >= n:
		return 1
	i, j = 1, 1
	for _ in xrange(n-2):
		i,j = i+j, i
	return i

def fib(n):
	if (n < 2):
		return n
	else:
		return fib(n - 1) + fib(n - 2)

if __name__ == '__main__':
	repeat = 1

	t1 = timeit.Timer('fibm(40)', 'from __main__ import fibm')
	t2 = timeit.Timer('fibd(40)', 'from __main__ import fibd')
	t3 = timeit.Timer('fib(40)', 'from __main__ import fib')

	print 'memoize decorator: ', t1.timeit(repeat)
	print 'fib fast: ', t2.timeit(repeat)
	print 'default slow: ', t3.timeit(repeat)