#!/usr/bin/env python3 # An example of using Python decorators to implement memoisation # Based on this online article: http://www.artima.com/weblogs/viewpost.jsp?thread=240808 # by Bruce Eckel # tracing function calls, using a class-based decorator class trace_class(object): """Perform memoisation on the 1-argument function @func@, with @n@ as argument.""" def __init__(self, f): print(".. trace_class.__init__\n") self.f = f def __call__(self, n): print("++ computing", self.f.__name__," with ", str(n)) return self.f(n) # memoisation decorator, implemented as a class class memoise_class(object): """Perform memoisation on the 1-argument function @func@, with @n@ as argument.""" def __init__(self, f): print(".. memoise_class.__init__\n") self.f = f def __call__(self, n, memo_dict=dict()): assert not(memo_dict is None) if n in memo_dict.keys(): # print("!! Found "+str(n)+" in memo dictionary\n") return memo_dict[n] else: print("++ computing", self.f.__name__," with ", str(n)) x = self.f(n) memo_dict[n] = x print(".. keys in memo_dict: ", str(memo_dict.keys())); return x # plain old fib # use a trace decorator to show all function calls to fib # use a memoise decorator to remember values from previous calls #@trace_class @memoise_class def fib(n): """Compute Fibonacci number of @n@.""" if n==0 or n==1: return 1 else: return fib(n-1)+fib(n-2) # Main ------------------------------------------------------- # depending on decoration above, this uses memoisation; the code here is unchanged! print(fib(8))