How to memoize functions?

[Steve Holden]

"Chris Reedy" <creedy at mitretek.org> wrote in message
news:3efc5383_6 at corp.newsgroups.com...
> Jerome Alet wrote:
> > Le Thu, 26 Jun 2003 16:29:07 -0400, Chris Reedy a écrit :
> >
> >
> >>The obvious way to memoize a function would be to keep a dictionary with
> >>keys being tuples (or maybe dictio naries) 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.
> >
> >
> > first I must say that my answer is probably completely stupid.
> >
> > however why would you want to use the original arguments tuple as a key
?
>
> Actually, I chose that just because it was the most obvious. The next
> choice was a tuple of the ids of the arguments ...
>
That wouldn't have been a very good choice, however, since memoizing
requires checks for argument-set equality, not argument identity.

> > depending on the computational intensity of your original function, why
> > not compute some sort of hash (like an hex md5sum) on all the arguments
> > (converted to strings and concatenated) ?
>
> This is certainly a possibility. However ...
>
> > this way your original arguments would still be garbage collectable
(well,
> > at least I suppose), since only the hash would be used for the key.
>
> That's true. Unfortunately, that misses the other half of the problem
> (which, admittedly, I didn't mention) which is that I would also like to
> be able to collect the results of the function, which could be complex
> data structures, as well as the arguments (which could be other
> instances of the same complex structures).
>
Well, if you weren't collecting the results you wouldn't be memoizing, would
you?

regards
--
Steve Holden                                  http://www.holdenweb.com/
Python Web Programming                 http://pydish.holdenweb.com/pwp/