Wandering Thoughts archives

2006-03-16

A tricky memoization decorator

This is the kind of hack where I present the Python code first and explain it later:

def memo1(func):
  def _wrap(self):
    r = func(self)
    setattr(self, func.func_name, \
            lambda : r)
    return r
  return _wrap

class Foo(object):
  ...
  def invar(self):
    return complex(self.field1) or \
           complex2(self.field2)
  invar = memo1(invar)

Here, invar is a method that computes some function of the object, with a value that never changes over the life of a given object. The computation is more expensive than we like, so we don't want to call it more than once, but it may never be called so it's not worth precomputing the result in __init__. Clearly, memoization to the rescue.

Ordinary memoization would store the result in a variable somewhere, and check it, and so on. We don't bother; instead, memo1 stores the result by rewriting the object's invar method to be a lambda expression that just returns the value, which is about as efficient as you can get. (It introspects the function it's wrapping to find out what name to rewrite, which rules out certain method tricks.)

One subtlety here is that the lambda takes no arguments, not a self argument that it ignores. A function that is added to an object instead of a class is not subject to the normal process of method lookup, so does not get called with any implicit self.

I would rather do the memoization in something like memo1 than in invar itself, because doing it in a decorator keeps the invar function itself clean and obvious. While the lambda rewrite version does perform somewhat better than the traditional memoization scheme, the bigger attraction of it to me is that it's just simpler; the code doesn't have to play games to find a storage spot for the result. (Tastes are quite likely to differ here.)

Unfortunately there is no way to pull this trick with properties; once a variable in a class is a property, you cannot turn it into an ordinary variable for a single object. In some situations doing this would be nice, because calling a lambda function is a bit over two times slower than accessing an object variable on my machine.

Sidebar: a more traditional memo1

Because I wrote it to do timing tests, here's a version of memo1 that doesn't use lambda rewriting:

def memo1(func):
  s = []
  def _wrap(self):
    if s:
      return s[0]
    r = func(self)
    s.append(r)
    return r
  return _wrap

There is probably a cleverer place to store the return value.

python/TrickyDecorator written at 02:22:15; Add Comment


Page tools: See As Normal.
Search:
Login: Password:
Atom Syndication: Recent Pages, Recent Comments.

This dinky wiki is brought to you by the Insane Hackers Guild, Python sub-branch.