How to memoize functions?

[sismex01 at hebmex.com]

> From: Chris Reedy [mailto:creedy at mitretek.org] 
> 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.
>

Yup.

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

Yup.

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

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