How to memoize functions?

Chris Reedy 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:>

   Given:

     def foo(a,b,c):
       return <result of large ugly computation>

   Memoization of foo would look like:

     def foo(a,b,c):
       if <this set of arguments has already been handled>
         return <result of prior computation>
       else
         <do large ugly computation>
         <save result>
         return <result>

</Aside>

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

   Thanks in advance, Chris





More information about the Python-list mailing list