Memoization made easy

What you need to know :
  1. Memoization
  2. Python decorators
Here is fib.py
def fibo (n) :
    print "fibo called with arg :", n
    if n in (0, 1): return 1
    else : return fibo (n-1) + fibo (n-2)

print fibo (5)
# prints
# fibo called with arg : 5
# fibo called with arg : 4
# fibo called with arg : 3
# fibo called with arg : 2
# fibo called with arg : 1
# fibo called with arg : 0
# fibo called with arg : 1
# fibo called with arg : 2
# fibo called with arg : 1
# fibo called with arg : 0
# fibo called with arg : 3
# fibo called with arg : 2
# fibo called with arg : 1
# fibo called with arg : 0
# fibo called with arg : 1
# 8

print fibo (3)
# prints
# fibo called with arg : 3
# fibo called with arg : 2
# fibo called with arg : 1
# fibo called with arg : 0
# fibo called with arg : 1
# 3

# Too bad!!
# So much redundant computation.
# Let's make it better!

from memoization import *

@memoize
def fib (n) :
    print "fib called with arg :", n
    if n in (0, 1): return 1
    else : return fib (n-1) + fib (n-2)


print fib (5)
# prints
# fib called with arg : 5
# fib called with arg : 4
# fib called with arg : 3
# fib called with arg : 2
# fib called with arg : 1
# fib called with arg : 0
#8

print fib (3)
# prints
# 3
Here is memoization.py
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
_mem_tbls_ = {}
def memoize (function) :
    global _mem_tbls_
    _mem_tbls_ [function] = {}
    def memoized_function (*args) :
        func_mem_tbl = _mem_tbls_ [function]
        if args not in func_mem_tbl :
            func_mem_tbl [args] = function (*args)
        return func_mem_tbl [args]
    return memoized_function

4 comments :

  1. If you have a couple of memoizations running in the same program, print mem_tbl finally, so that the reader will get a feel for your memoization.py code... I am still awestruck by the fact that _mem_tbls_ [function] works - a dictionary of lists right?
    -pyNoob

    Reply Delete
  2. ^ A dictionary of dictionaries actually.

    Reply Delete

Post a Comment

Note: Only a member of this blog may post a comment.