How to memoize functions?

Discussion in 'Python' started by Chris Reedy, Jun 26, 2003.

  1. Chris Reedy

    Chris Reedy Guest

    I would like to memoize (I think I've got that right) a collection of
    functions for a project I'm working.

    <Aside for those not familiar with memoizing functions:>

    Given:

    def foo(a,b,c):
    return <result of large ugly computation>

    Memoization of foo would look like:

    def foo(a,b,c):
    if <this set of arguments has already been handled>
    return <result of prior computation>
    else
    <do large ugly computation>
    <save result>
    return <result>

    </Aside>

    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. Something like
    weakref.WeakKeyDictionary seems to be the obvious solution. 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).

    Thanks in advance, Chris
    Chris Reedy, Jun 26, 2003
    #1
    1. Advertising

  2. Chris Reedy

    Jerome Alet Guest

    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 ?

    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 way your original arguments would still be garbage collectable (well,
    at least I suppose), since only the hash would be used for the key.

    again, it may be stupid, I don't know python internal enough

    hth

    Jerome Alet
    Jerome Alet, Jun 26, 2003
    #2
    1. Advertising

  3. Chris Reedy

    Jeff Epler Guest

    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.

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

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

    Jeff
    Jeff Epler, Jun 26, 2003
    #3
  4. Chris Reedy

    Chris Reedy Guest

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

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

    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! =-----
    Chris Reedy, Jun 27, 2003
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    0
    Views:
    648
  2. Replies:
    2
    Views:
    758
  3. Michael Hohn
    Replies:
    3
    Views:
    1,094
    Dima Dorfman
    Oct 31, 2004
  4. Replies:
    11
    Views:
    616
    Gabriel Genellina
    Aug 19, 2006
  5. thebjorn
    Replies:
    4
    Views:
    307
    Michele Simionato
    Dec 20, 2007
Loading...

Share This Page