Memoization/Caching of Instance Methods

Mark E. Fenner Hobbes2176 at yahoo.com
Thu Mar 24 23:01:56 CET 2005


In the code below, the class DifferentCache utilizes three different
memoization (caching) strategies.  Neither the function Memoize1 or
the class Memoize2 will be adequate for all three of these cases (I
intend these to be used as, for example, 
getInstanceValueFunction = Memoize1(getInstanceValueFunction) 
within the DifferentCache class definition).


Memoize1 will have problems with getMemberValueFunction b/c it
will try to generate a cache key for (self, 'arg1', 'arg2') whereas
the actual values only depend on ('val1', 'val2') (though this may be
more of a nuisance then an error).

Memoize2 will have problems with getInstanceValueFunction b/c
instantiating Memoize2 will cause 'self' to refer to the Memoize2
object and not to the DifferentCache object when computing the desired
function (and worse yet, since the self that does reference
DifferentCache is bound to the DifferentCache.getInstanceValueFunction
it is not even passed in as an argument when Memoize2.__call__ is
executed .... apologies if my terminology is off).  Actually, would
this problem apply to any use of Memoize2 to any instance method?
Also, for any of these memoizations, there is only 1 self so we really
don't need it as a cache key.

Both Memoize methods will have problems, in addition, b/c the hashing
for an object is based on __str__ which should also be Memoized --
that is, there is a circular dependency of __hash__ on __str__ and of
__str__ on __hash__.  Perhaps a generator that computed the value the first
time and then subsequently return that value from a stored variable?

Obviously, you could deal with these problems by simply keeping each
individual cacheing strategy for the different methods.  However, can
anyone see how to unify these into a common cacheing mechanism?  Or,
can it be handled by some careful rewriting of how the functions
(methods) are called?


#
# from ?? on comp.lang.python
#
def Memoize1(func):
    cache = {}
    def _internal(*args):
        if cache.has_key(args):
            return cache[args]
        else:
            ans = cache[args] = func(*args)
            return ans
    return _internal

#
# from Peter norvig on comp.lang.python
#
class Memoize2:
    def __init__(self, fn):
        self.cache={}
        self.fn=fn
    def __call__(self,*args):
        if self.cache.has_key(args):
            return self.cache[args]
        else:
            object = self.cache[args] = self.fn(*args)
            return object


#
# an example class
#
class DifferentCache:
    def __init__(self, value):
        self.value = value
        self.complexValueCache = {}

    def getInstanceValueFunction(self):
        try:
            value = self.instanceValueCache
        except KeyError:
            value = self.instanceValueCache = someFunction(self)
        return value

    def getMemberValueFunction(self, other1, other2):
        try:
            value =  self.complexValueCache[other]
        except KeyError:
            value = self.complexValueCache[other] = \
                    someOtherFunction(self, other1, other2))
        return value

    def __str__(self):
        try:
            strValue = self.stringCache
        except AttributeError:
            strValue = self.stringCache = str(self.value)
        return strValue

    def nonCachedFunction(self):
        return yetAnotherFunction(self)

    def __hash__(self):
        return str.__hash__(str(self))     


#
# Desired rewrite or so
#
class DifferentCache:
    def __init__(self, value):
        self.value = value

    @Memoized
    def getInstanceValueFunction(self):
        return someFunction(self)

    @Memoized
    def getMemberValueFunction(self, other1, other2):
        return someOtherFunction(self, other1, other2)

    @Memoized
    def __str__(self):
        return str(self.value)

    def nonCachedFunction(self):
        return yetAnotherFunction(self)

    def __hash__(self):
        return str.__hash__(str(self))     

Note, the various functions within the instance methods are meant to
represent some arbitrary code executed on and computing values from the
various arguments.




More information about the Python-list mailing list