Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > RE: How to memoize functions?

Thread Tools

RE: How to memoize functions?
Posts: n/a
> From: Chris Reedy [(E-Mail Removed)]
> Sent: Jueves, 26 de Junio de 2003 03:29 p.m.
> 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.

Why is this an objection? What kind of objects are in the
argument tuples?

If storing the tuples is a problem, you could use instead
the hash value for the tuple; if you can be sure that no
collisions will occur, just change the above implementation:

class MemoizeFunction:
hashfunc = hash
def __init__(self, function):
self.function = function
self.memo = {}
def __call__(self, *args):
h = self.hashfunc(args)
if h not in self.memo:
self.memo[h] = self.function(*args)
return self.memo[h]

So now the argument tuples won't be stored, only their hash.
Now, having the correct hash function is important.

> Something like weakref.WeakKeyDictionary seems to be the
> obvious solution.

And, it's a whole new and improved can of worms.
What happens when a weakref dies? You have to delete
the memo dictionary's relevant entry, right? So,
when any of the argument objects leave scope and
die, your memo dies also. :-/

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

Seems to me that the best approach is to generate a hash function
from the argument tuple, and memoize in base of that hash value.

I don't think weakrefs will help you much here.

> Thanks in advance, Chris

Advertencia:La informacion contenida en este mensaje es confidencial y
restringida, por lo tanto esta destinada unicamente para el uso de la
persona arriba indicada, se le notifica que esta prohibida la difusion de
este mensaje. Si ha recibido este mensaje por error, o si hay problemas en
la transmision, favor de comunicarse con el remitente. Gracias.

Reply With Quote

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off

Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: How include a large array? Edward A. Falk C Programming 1 04-04-2013 08:07 PM
efficient memoize decorator? Python 11 08-19-2006 12:27 PM
AssertionError in pickle's memoize function Michael Hohn Python 3 10-31-2004 03:13 PM
RE: How to memoize functions? Python 2 06-27-2003 05:25 PM
How to memoize functions? Chris Reedy Python 3 06-27-2003 02:18 PM