Python func_dict used to memoize; other useful tricks?

Question

A Python function object has an attribute dictionary called `func_dict` which is visible from outside the function and is mutable, but which is not modified when the function is called. (I learned this from answers to a question I asked yesterday (#1753232): thanks!) I was reading code (at http://pythonprogramming.jottit.com/functional_programming) which memoized the computation of Fibonacci numbers and thought, "Why not use the `func_dict` attribute for memoizing?" It worked (see below; the output's at the end of the code.). It's a little like having a class property available but having the initialization code outside the object (in this case, not a class but a function). I wonder what similar (or dissimilar) tricks can be done using this attribute? ``` def fib(n): if n in fib.cache: print "found fib.cache[%d] = %d: " %(n, fib.cache[n]) return fib.cache[n] else: print "fib.cache[%d] = fib(%d) + fib(%d)" % (n, n-1, n-2) fib.cache[n] = fib(n-1) + fib(n-2) print "modified fib.cache: ",…

Accepted Answer

Just be careful: the `fib.cache` trick only works if `fib` is indeed the name of the relevant function object in the scope that's active while it's executing (for example, when you decorate it as you have done, you must assign the starting value for the cache to the decorator wrapper, not to the decorated function -- and if it gets further decorated after that, things break).

This is a bit fragile compared to the standard memoization idiom:

```
def fib(n, _memo={0:1, 1:1}):
    if n in _memo:
        return _memo[n]
    else:
        _memo[n] = fib(n-1) + fib(n-2)
        return _memo[n]
```

or the decorator equivalent. The standard idiom's also faster (though not by much) -- putting them both in mem.py under names fib1 (the .cache-trick one, without prints and undecorated) and fib2 (my version), we see...:

```
$ python -mtimeit -s'import mem' 'mem.fib1(20)'
1000000 loops, best of 3: 0.754 usec per loop
$ python -mtimeit -s'import mem' 'mem.fib2(20)'
1000000 loops, best of 3: 0.507 usec per loop
```

so the standard-idiom version saves about 33% of the time, but that's when almost all calls do actually hit the memoization cache (which is populated after the first one of those million loops) -- fib2's speed advantage is smaller on cache misses, since it comes from the higher speed of accessing `_memo` (a local variable) vs `fib.cache` (a global name, fib, and then an attribute thereof, cache), and cache accesses dominate on cache hits (there's nothing else;-) but there's a little extra work (equal for both functions) on cache misses.

Anyway, don't mean to rain on your parade, but when you find some new cool idea be sure to measure it against the "good old way" of doing things, both in terms of "robustness" and performance (if you're caching, presumably you care about performance;-).

Python func_dict used to memoize; other useful tricks?

Solution

Problem

Related problems