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

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

Python, 50 lines
 1
 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.

2 comments

Paul Whipp 9 years, 10 months ago  # | flag

Nice and very handy for quick performance enhancements here and there.

What are lines 6 to 10 for exactly?

Jens Weggemann 9 years, 7 months ago  # | flag

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.

Created by Foo Bar on Tue, 11 Jul 2006 (PSF)
Python recipes (4591)
Foo Bar's recipes (1)

Required Modules

Other Information and Tasks