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

# Memoize Decorator Function With Cache Size Limit (python Recipe)
#
# 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.
#
# http://code.activestate.com/recipes/496879-memoize-decorator-function-with-cache-size-limit/

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