Welcome, guest | Sign In | My Account | Store | Cart

Minimalistic Memoization in python, just works, doesn't take care of cleaning up the cache however.

Python, 16 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def fib(n):
    if n==1 or n==0:
        return 1
    return fib(n-2) + fib(n-1)


def memoize(f):
    cache= {}
    def memf(*x):
        if x not in cache:
            cache[x] = f(*x)
        return cache[x]
    return memf

fib = memoize(fib)
print fib(969)

2 comments

Ashish Yadav 13 years, 11 months ago  # | flag

If we use memoize function as a python decorator, than IMHO code looks more pythonic Don't know though if decorators were not used on purpose.

def memoize(f):
    cache= {}
    def memf(*x):
        if x not in cache:
            cache[x] = f(*x)
        return cache[x]
    return memf

@memoize
def fib(n):
    if n==1 or n==0:
        return 1
    return fib(n-2) + fib(n-1)


print fib(969)
Ahmed El Deeb (author) 13 years, 11 months ago  # | flag

Well, I quite agree. This is neater and more pythonic.

In the first code snippet, I was also trying to show (in a presentation to some colleagues) what it means for functions to be first class citizens in a language, i.e. you can pass functions as parameters to other functions, you can return functions as return values from other functions, and you can assign them to variable names.

It also would work if the function is not your code, but imported from some other script, and it will affect this function only in the local context or scope.

Finally, I am not quite familiar with decorators to be honest :) will work on that.

Created by Ahmed El Deeb on Thu, 6 May 2010 (MIT)
Python recipes (4591)
Ahmed El Deeb's recipes (2)

Required Modules

  • (none specified)

Other Information and Tasks