# A Memoize Decorator for Python Recursive Functions

This shows the application of a Memoize decorator to speed up recursive functions in Python.

Lucaci Andrew commented: Nice one. +5
BustACode commented: Good stuff. Looks to also be my entry into decorators. +0
522 Views

Scientist

``````''' decorator_Memoize1.py
applying a memoize decorator to a recursive function
and timing to show the improvement in speed
No keyword args allowed in the decorated function!
works with Python27 and Python33
'''

import timeit

class Memoize(object):
"""
use as a decorator to avoid repeating calculations
previously done by the decorated function
(do not use for functions with keyword arguments)
"""
def __init__(self,f):
self.f = f
self.memo = {}
def __call__(self,*args):
if args in self.memo:
return self.memo[args]
result = self.f(*args)
self.memo[args] = result
return result

def use_timeit(stmt, setup, passes=1000000):
"""
use module timeit to time a statement stmt
(this can be a function call or a code segment)
for time consuming functions use fewer passes to save time
setup gives information where too find variables/functions
for instance -->
stmt = 'myfunction(x)'
setup = 'from __main__ import myfunction, x'
"""
t = timeit.Timer(stmt=stmt, setup=setup)
# 1000000 passes is default
# elapsed is the time in microseconds/pass
elapsed = (1000000//passes * t.timeit(number=passes))
print( "%s takes %0.3f micro-seconds/pass" % (stmt, elapsed) )

@Memoize
def fibo1(n):
"""
use recursion to get Fibonacci number for n
not very efficient because of the many function calls
"""
if n < 2:
return n
else:
return fibo1(n - 1) + fibo1(n - 2)

# timing ...
print("first pass:")
stmt = 'fibo1(30)'
setup = 'from __main__ import fibo1'
passes = 1
use_timeit(stmt, setup, passes)

print("second pass:")
stmt = 'fibo1(30)'
setup = 'from __main__ import fibo1'
passes = 1
use_timeit(stmt, setup, passes)

# testing ...
print(fibo1(30))  # 832040

""" result ...
with the @Memoize decorator ...
first pass:
fibo1(30) takes 106.077 micro-seconds/pass
second pass:
fibo1(30) takes 2.281 micro-seconds/pass

without (commented out) the @Memoize decorator ...
first pass:
fibo1(30) takes 875692.257 micro-seconds/pass
second pass:
fibo1(30) takes 877517.997 micro-seconds/pass
"""``````

vegaseat, this must be the commented out test version
replace
#@Memoize
with
@Memoize
to get the working version

``````""" result ...
with the @Memoize decorator ...
first pass:
fibo1(30) takes 106.077 micro-seconds/pass
second pass:
fibo1(30) takes 2.281 micro-seconds/pass
without (commented out) the @Memoize decorator ...
first pass:
fibo1(30) takes 875692.257 micro-seconds/pass
second pass:
fibo1(30) takes 877517.997 micro-seconds/pass
"""
``````

Or wasn't that clear enough?
His first test was indeed with `@Memoize`, 2nd was with that commented, so that the results yeld different timings.

I guess I am getting old and left the # in from the last timing test. I prefer to post a working version and corrected it, thanks.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.18 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.