How to memoize functions?
creedy at mitretek.org
Thu Jun 26 22:29:07 CEST 2003
I would like to memoize (I think I've got that right) a collection of
functions for a project I'm working.
<Aside for those not familiar with memoizing functions:>
return <result of large ugly computation>
Memoization of foo would look like:
if <this set of arguments has already been handled>
return <result of prior computation>
<do large ugly computation>
The obvious way to memoize a function would be to keep a dictionary with
keys being tuples (or maybe dictionaries) of previous argument lists
and values being the results of the previous computations.
Unfortunately, this will really mess up garbage collection, since
objects that are arguments could never be collected. Something like
weakref.WeakKeyDictionary seems to be the obvious solution. However, a
WeakKeyDictionary won't work since it can't use a tuple as a key, and
wouldn't do the right thing, even if it could.
The only solution I've got so far is to implement a new class, imitating
WeakKeyDictionary. I started down this road, but the implementation
started getting a little involved, since I needed two dictionaries, one
for the argument list -> result mapping and one to keep track of which
objects appear in which argument lists (since an argument tuple must be
deleted when _any_ of its arguments becomes garbage).
So ... does anyone have any suggestions and/or has anyone already done
something like this (I couldn't find anything in the cookbook at
Thanks in advance, Chris
More information about the Python-list