Dynamic Programming Memoization in Python

memoization.py

import functools


def memoization(mem_dict):
    """ This is a version for modules' functions.
        :Parameter - `mem_dict`
            A global variable used to store the calculation result
        :Usage
            fibo_dict = {}
            @memoization(fibo_dict)
            def fibo(n):
                # ...
    """
    def decorator(func):
        @functools.wraps(func)
        def wrapper(*args):
            # Can't use **kwargs atm. Any ways to use dict in dict?
            data = tuple(args)
            result = mem_dict.get(data, None)
            if not result:
                result = func(*args)
                mem_dict[data] = result
            return result
        return wrapper
    return decorator


def memoization_obj(func):
    """ This is a version for objects' methods.
        :Parameter - None
        :Usage
            class Hello(object):
                @memoization_obj
                def fibo(self, n):
                    # ...
    """

    attr_name = '_memoization_%s' % func.__name__

    @functools.wraps(func)
    def wrapper(*args):
        self = args[0]
        if not hasattr(self, attr_name):
            setattr(self, attr_name, {})
        mem_dict = getattr(self, attr_name)
        data = tuple(args)
        result = mem_dict.get(data, None)
        if not result:
            result = func(*args)
            mem_dict[data] = result
        return result
    return wrapper



if __name__ == '__main__':
    fibo_dict = {}

    @memoization(fibo_dict)
    def fibo(n):
        print '# Calculate Fibo(%d)' % n  # Trace
        if n <= 2:
            return 1
        print '    > Call Fibo(%d)' % (n - 1)  # Trace
        print '    > Call Fibo(%d)' % (n - 2)  # Trace
        return fibo(n - 1) + fibo(n - 2)

    class Fibonacci(object):
        @memoization_obj
        def fibo(self, n):
            print '# Calculate Fibo(%d)' % n  # Trace
            if n <= 2:
                return 1
            print '    > Call Fibo(%d)' % (n - 1)  # Trace
            print '    > Call Fibo(%d)' % (n - 2)  # Trace
            return self.fibo(n - 1) + self.fibo(n - 2)

    print "*** Module Function ***"
    fibo(6)
    print
    print "*** Object Method ***"
    f = Fibonacci()
    f.fibo(6)




#################### RESULT ####################

##### Module Function #####
# Calculate Fibo(6)
#    > Call Fibo(5)
#    > Call Fibo(4)
# Calculate Fibo(5)
#    > Call Fibo(4)
#    > Call Fibo(3)
# Calculate Fibo(4)
#    > Call Fibo(3)
#    > Call Fibo(2)
# Calculate Fibo(3)
#    > Call Fibo(2)
#    > Call Fibo(1)
# Calculate Fibo(2)
# Calculate Fibo(1)

##### Object Method #####
# Calculate Fibo(6)
#    > Call Fibo(5)
#    > Call Fibo(4)
# Calculate Fibo(5)
#    > Call Fibo(4)
#    > Call Fibo(3)
# Calculate Fibo(4)
#    > Call Fibo(3)
#    > Call Fibo(2)
# Calculate Fibo(3)
#    > Call Fibo(2)
#    > Call Fibo(1)
# Calculate Fibo(2)
# Calculate Fibo(1)