code.kerkeslager.com Git - sandbox/blob - memoization.py

   1 class Memoize(object):
   2         """
   3         Implements memoziation.  Use as a decorator to cache the results of a
   4         function.  The function must have the following properties:
   5         *       No side effects.
   6         *       Referentially transparent.
   7         *       No keyword arguments.
   8
   9         While the following are not required for proper behavior, memoization is
  10         unlikely to produce a significant performance gain and may indeed produce
  11         a performance loss unless the function has the following properties:
  12         *       Performance slower than a hash lookup on the arguments.
  13         *       The function is called many times with the same arguments.
  14         These properties occur most often when a function has deep and/or wide
  15         recursion.
  16
  17         For more information see the following links:
  18         *       http://en.wikipedia.org/wiki/Memoization
  19         *       http://en.wikipedia.org/wiki/Referential_transparency_(computer_science)
  20         """
  21         def __init__(self,f):
  22                 self.f = f
  23                 self.memo = {}
  24
  25         def __call__(self,*args):
  26                 if args in self.memo:
  27                         return self.memo[args]
  28
  29                 result = self.f(*args)
  30                 self.memo[args] = result
  31                 return result
  32
  33 class KWMemoize(object):
  34         """
  35         This is equivalent to Memoize except that it allows keyword arguments.
  36         However, there is a small performance cost for this so one should use
  37         Memoize for functions that do not take keyword arguments.
  38         """
  39         def __init__(self,f):
  40                 self.f = f
  41                 self.memo = {}
  42
  43         def __call__(self,*args,**kwargs):
  44                 kws = tuple(kwargs.items())
  45
  46                 if (args,kws) in self.memo:
  47                         return self.memo[(args,kws)]
  48
  49                 result = self.f(*args,**kwargs)
  50                 self.memo[(args,kws)] = result
  51                 return result