Yet another memoize decorator, except with a cache size limit with an LRU policy.
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 | 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
|
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.
Nice and very handy for quick performance enhancements here and there.
What are lines 6 to 10 for exactly?
Paul,
That confused me a bit at first as well, but I can explain. Firstly, a decorator without arguments
@memoize def foo(): pass
is, of course, equivalent to memoize(foo) and calls to foo are like memoize(foo)(...args...) On the other hand, used with an argument like
@memoize(100) def foo(): pass
it is equivalent to memoize(100)(foo) and calls to foo are equivalent to memoize(100)(foo)(...args...), i.e. an extra level of indirection. This decorator supports both use cases with a nice little trick.
In the argument-less case, the function argument will be the actual function, not the limit (an int), and hence the code in lines 6-10 is skipped and the wrapper is returned directly.
The second use case calls memoize() with the limit in the function slot... this is recognized with the isinstance() call and will return a simple wrapper that in turn returns the original memoize function (with the arguments fixed, remember that the function argument holds the limit value at that point), thus balancing out the extra indirection of this use case.