RE: How to memoize functions?

Discussion in 'Python' started by sismex01@hebmex.com, Jun 26, 2003.

  1. Guest

    > From: Chris Reedy [mailto:]
    > 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.
     
    , Jun 26, 2003
    #1
    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. Chris Reedy

    How to memoize functions?

    Chris Reedy, Jun 26, 2003, in forum: Python
    Replies:
    3
    Views:
    1,009
    Chris Reedy
    Jun 27, 2003
  2. Replies:
    2
    Views:
    778
  3. Michael Hohn
    Replies:
    3
    Views:
    1,160
    Dima Dorfman
    Oct 31, 2004
  4. Replies:
    11
    Views:
    641
    Gabriel Genellina
    Aug 19, 2006
  5. thebjorn
    Replies:
    4
    Views:
    333
    Michele Simionato
    Dec 20, 2007
Loading...

Share This Page