Memoizing Generators

Mark Hobbes2176 at yahoo.com
Wed Jul 9 00:28:37 CEST 2003


Hello all,

Peter Norvig has a great recipe for memoizing Python functions available at 
http://www.norvig.com/python-iaq.html .  I made good use of this until I
tried to memoize a generator.  At this point, it breaks down because the
_generator_ object is stored as the value for the *args key.

So, I came up with this:

class MemoizeGenerator:
    def __init__(self, fn):
        self.cache={}
        self.fn=fn
    def __call__(self,*args):
        if self.cache.has_key(args):
            for _i in self.cache[args]:
                yield _i
        else:
            self.cache[args]=()
            for _i in self.fn(*args):
                self.cache[args]+=(_i,)
                yield _i

Basically, if the generator hasn't been called before with these args, it
will run the generator's iterator through and append a tuple in the
dictionary value field for these keys.  If the args have been used before,
then it iterates through the previously computed list.  It works like a
charm for me.

Now, the two remaining issues are 1) can we "unify" the generator
memoization with the "standard" memoization and 2) can we deal with lists
as well (i.e. my generator was returning tuples ... since I'm scared of
lists in recursive generator contexts *wink*).  One other memoization
issues:  what if the args (which will become keys) are mutables ... in
particular, lists.  I suppose we could just tuple() them up?

Regards,
Mark




More information about the Python-list mailing list