Title: Memoize decorator function with cache size limit
Submitter: John McNeil (other recipes)
Last Updated: 2006/07/11
Version no: 1.0
Category: Algorithms

Description:

Yet another memoize decorator, except with a cache size limit with an LRU policy.

Source: Text Source

import cPickle

__all__ = ["memoize"]

def memoize(function, limit=None):
    if isinstance(function, int):
        def memoize_wrapper(f):
            return memoize(f, function)

        return memoize_wrapper

    dict = {}
    list = []
    def memoize_wrapper(*args, **kwargs):
        key = cPickle.dumps((args, kwargs))
        try:
            list.append(list.pop(list.index(key)))
        except ValueError:
            dict[key] = function(*args, **kwargs)
            list.append(key)
            if limit is not None and len(list) > limit:
                del dict[list.pop(0)]

        return dict[key]

    memoize_wrapper._memoize_dict = dict
    memoize_wrapper._memoize_list = list
    memoize_wrapper._memoize_limit = limit
    memoize_wrapper._memoize_origfunc = function
    memoize_wrapper.func_name = function.func_name
    return memoize_wrapper

# Example usage
if __name__ == "__main__":
    # Will cache up to 100 items, dropping the least recently used if
    # the limit is exceeded.
    @memoize(100)
    def fibo(n):
        if n > 1:
            return fibo(n - 1) + fibo(n - 2)
        else:
            return n

    # Same as above, but with no limit on cache size
    @memoize
    def fibonl(n):
        if n > 1:
            return fibo(n - 1) + fibo(n - 2)
        else:
            return n

Discussion:

Memoization caches the result of a function call and returns the cached value whenever the function is called with the same arguments, instead of recomputing it. This is especially useful with expensive functions which you know will always return the same values, given the same arguments.

All variables used by the wrapper between calls are stored on it, so the limit can be altered after creation, or the dict or list can be modified if required (though you should be careful to make any changes to *both*; they're intended for internal use only, so the wrapper assumes they'll always be in a consistent state). Additionally, the original function is stored on it in case access to it is requied, and the name is changed to match that of the original function, mostly for if it needs to be used in the interactive interpreter.