How to memoize functions?

Chris Reedy creedy at mitretek.org
Fri Jun 27 10:39:38 EDT 2003


Jeff Epler wrote:
> The argument tuple is only "materialized" for a moment (it disappears
> after the called function returns, if it was taken by *args, or else
> before the first line of the function if it was taken by named args).
> It will disappear from a weakkeydict immediately as a result.  

Yeah. I'd already recognized that problem.

> The common memoize, written here using nested scopes, never trims old
> values from the dictionary:
>     def memoize(f):
>         d = {}
>         def g(*args):
>             if not d.has_key(args):
>                 d[args] = f(*args)
>             return d[args]
>         return g

Nice. I tried it and it also appears to work for methods, e.g.:
   class foo:
     def f(...): ...
     f = memoize(f)

> You could make d be a cache of limited size with code like
>             if not d.has_key(args):
>                 if len(d) > 1000:
>                     d.pop() # XXX
>                 d[args] = f(*args)
> the XXX line removes "some key" from the dictionary.  The actual item is
> not specified, but turns out to have some relationship to the hash value
> of args.  This may or may not be acceptable to you.  Otherwise, you might
> implement a true pseudorandom replacement algorithm, or the standard LRU,
> or LFU.  These may require that you maintain a heap or other auxiliary
> list (corresponding to the keys) to achieve O(1) for the "remove an old
> memoized value" code.

The more I think about this, the more I like it. It solves another 
problem I was having, which is that re-computation for the same set of 
arguments is most likely for recent computations.

> I just think weakrefs are not the solution to this problem...

Just out of curiosity, what's the problem with weak refs. Are they too 
new to depend on or are they carrying some other baggage that's not 
obvious from the documentation.

   Chris



-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----==  Over 80,000 Newsgroups - 16 Different Servers! =-----




More information about the Python-list mailing list