Function decorator that caches function results

[Lasse Vågsæther Karlsen]

After working through a fair number of the challenges at 
www.mathschallenge.net, I noticed that some long-running functions can 
be helped *a lot* by caching their function results and retrieving from 
cache instead of calculating again. This means that often I can use a 
natural recursive implementation instead of unwinding the recursive 
calls to avoid big exponential running-times.

Ok, so I thought, how about creating a decorator that caches the 
function results and retrieves them from cache if possible, otherwise it 
calls the function and store the value in the cache for the next invokation.

This is what I came up with so far:

def cache_function(fn):
     cache = {}
     def cached_result(*args, **kwargs):
         if args in cache:
             return cache[args]
         result = fn(*args, **kwargs)
         cache[args] = result
         return result
     return cached_result

Example of usage:

@cache_function
def fibonacci(idx):
     if idx in (1, 2):
         return 1
     else:
         return fibonacci(idx-1) + fibonacci(idx-2)

for index in range(1, 101):
     print index, fibonacci(index)

this example goes from taking exponential time to run to being near 
instantaneous.

However, this:

for index in range(1, 101):
     print index, fibonacci(idx = index)

this one uses the kwargs list of arguments, and I'm not sure how to 
change my function to take that into account.

Does anyone have any clues as to how to do that?

The solution would have to consider fibonacci(50) and fibonacci(idx = 
50) as the same call and thus retrieve the second one from the cache.

-- 
Lasse Vågsæther Karlsen
http://usinglvkblog.blogspot.com/
mailto:lasse at vkarlsen.no
PGP KeyID: 0x2A42A1C2