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: ", fib.cache
        return fib.cache[n]

fib.cache = {0:0, 1:1}

for x in range(7):
    print "==================>", x
    print fib( x)

"""
==================> 0
found fib.cache[0] = 0: 
0
==================> 1
found fib.cache[1] = 1: 
1
==================> 2
fib.cache[2] = fib(1) + fib(0)
found fib.cache[1] = 1: 
found fib.cache[0] = 0: 
modified fib.cache:  {0: 0, 1: 1, 2: 1}
1
==================> 3
fib.cache[3] = fib(2) + fib(1)
found fib.cache[2] = 1: 
found fib.cache[1] = 1: 
modified fib.cache:  {0: 0, 1: 1, 2: 1, 3: 2}
2
==================> 4
fib.cache[4] = fib(3) + fib(2)
found fib.cache[3] = 2: 
found fib.cache[2] = 1: 
modified fib.cache:  {0: 0, 1: 1, 2: 1, 3: 2, 4: 3}
3
==================> 5
fib.cache[5] = fib(4) + fib(3)
found fib.cache[4] = 3: 
found fib.cache[3] = 2: 
modified fib.cache:  {0: 0, 1: 1, 2: 1, 3: 2, 4: 3, 5: 5}
5
==================> 6
fib.cache[6] = fib(5) + fib(4)
found fib.cache[5] = 5: 
found fib.cache[4] = 3: 
modified fib.cache:  {0: 0, 1: 1, 2: 1, 3: 2, 4: 3, 5: 5, 6: 8}
8
"""

Answer 1

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;-).

Answer 2

I've always used this technique for memoizing. It uses the fact that you can call an object that's not a function, so long as that object has its __call__ method defined. Neither behindthefall's method, nor Alex Martelli's even occurred to me, for whatever reason. I would guess the performance is roughly the same as behindthefall's way, because it works roughly the same way. Maybe a little slower. But as the linked page points out, "the definition for fib() is now the "obvious" one, without the cacheing code obscuring the algorithm" which is kind of nice.