Cached Functions and Methods

AUTHORS:

  • William Stein (inspired by conversation with Justin Walker).
  • Mike Hansen (added doctests and made it work with class methods).
  • Willem Jan Palenstijn (add CachedMethodCaller for binding cached methods to instances).
  • Tom Boothby (added DiskCachedFunction).
  • Simon King (improved performance, more doctests).
class sage.misc.cachefunc.CachedFunction(f, classmethod=False)

Bases: object

Create a cached version of a function, which only recomputes values it hasn’t already computed. Synonyme: cached_function

If f is a function, do either g = CachedFunction(f) or g = cached_function(f) to make a cached version of f, or put @cached_function right before the definition of f (i.e., use Python decorators):

@cached_function
def f(...):
    ....

The inputs to the function must be hashable.

EXAMPLES:

sage: @cached_function
... def mul(x, y=2):
...     return x*y
...
sage: mul(3)
6

We demonstrate that the result is cached, and that, moreover, the cache takes into account the various ways of providing default arguments:

sage: mul(3) is mul(3,2)
True
sage: mul(3,y=2) is mul(3,2)
True

The user can clear the cache:

sage: a = mul(4)
sage: mul.clear_cache()
sage: a is mul(4)
False

It is also possible to explicitly override the cache with a different value:

sage: mul.set_cache('foo',5)
sage: mul(5,2)
'foo'
clear_cache()

Clear the cache dictionary.

EXAMPLES:

sage: g = CachedFunction(number_of_partitions)
sage: a = g(5)
sage: g.get_cache()
{((5, None, 'default'), ()): 7}
sage: g.clear_cache()
sage: g.get_cache()
{}
get_cache()

Returns the cache dictionary.

EXAMPLES:

sage: g = CachedFunction(number_of_partitions)
sage: a = g(5)
sage: g.get_cache()
{((5, None, 'default'), ()): 7}
get_key(*args, **kwds)

Returns the key in the cache to be used when args and kwds are passed in as parameters.

EXAMPLES:

sage: @cached_function
... def foo(x):
...    return x^2
...
sage: foo(2)
4
sage: foo.get_key(2)
((2,), ())
sage: foo.get_key(x=3)
((3,), ())
is_in_cache(*args, **kwds)

Checks if the argument list is in the cache.

EXAMPLES:

sage: class Foo:
...       def __init__(self, x):
...           self._x = x
...       @cached_method
...       def f(self, z, y=0):
...           return self._x*z+y
...
sage: a = Foo(2)
sage: a.f.is_in_cache(3)
False
sage: a.f(3)
6
sage: a.f.is_in_cache(3,y=0)
True
precompute(arglist, num_processes=1)

Cache values for a number of inputs. Do the computation in parallel, and only bother to compute values that we haven’t already cached.

EXAMPLES:

sage: @cached_function
... def oddprime_factors(n):
...     l = [p for p,e in factor(n) if p != 2]
...     return len(l)
sage: oddprime_factors.precompute(range(1,100), 4)
sage: oddprime_factors(25) is oddprime_factors(25)
True
set_cache(value, *args, **kwds)

Set the value for those args and keyword args Mind the unintuitive syntax (value first). Any idea on how to improve that welcome!

EXAMPLES:

sage: g = CachedFunction(number_of_partitions)
sage: a = g(5)
sage: g.get_cache()
{((5, None, 'default'), ()): 7}
sage: g.set_cache(17, 5)
sage: g.get_cache()
{((5, None, 'default'), ()): 17}
sage: g(5)
17

DEVELOPER NOTE:

Is there a way to use the following intuitive syntax?

sage: g(5) = 19    # todo: not implemented
sage: g(5)         # todo: not implemented
19
class sage.misc.cachefunc.CachedInParentMethod(f)

Bases: sage.misc.cachefunc.CachedMethod

A decorator that creates a cached version of an instance method of a class.

In contrast to CachedMethod, the cache dictionary is an attribute of the parent of the instance to which the method belongs.

ASSUMPTION:

This way of caching works only if

  • the instances have a parent,
  • the parent allows assignment of attributes, and
  • the instances are hashable (they are part of the cache key).

NOTE:

For proper behavior, the method must be a pure function (no side effects). Arguments to the method must be hashable.

EXAMPLES:

sage: class MyParent(Parent):
...       pass
...
sage: class Foo:
...       def __init__(self, x):
...           self._x = x
...       _parent = MyParent()
...       def parent(self):
...           return self._parent
...       def __eq__(self, other):
...           return self._x^2 == other._x^2
...       def __hash__(self):
...           return hash(self._x^2)
...       def __repr__(self):
...           return 'My %s'%self._x
...       @cached_in_parent_method
...       def f(self):
...           return self._x^3
...
sage: a = Foo(2)
sage: a.f()
8
sage: a.f.get_cache()   #indirect doctest
{(My 2, ((), ())): 8}

Since the key for the cache depends on equality of the instances, we obtain identical result for equal instances - even though in this particular example the result of the method should be different for a and b:

sage: b = Foo(-2)
sage: a is not b
True
sage: a == b
True
sage: b.f() is a.f()
True

Non-equal instances do not share the result of the cached method, but they do share the cache:

sage: c = Foo(3)
sage: c.f()
27
sage: c.f.get_cache() is a.f.get_cache() #indirect doctest
True

Note that the cache is also available as an attribute of the cached method, which speeds up internal computations:

sage: a.f.cache is b.f.get_cache() is c.f._cachedmethod._get_instance_cache(c)
True
class sage.misc.cachefunc.CachedMethod(f)

Bases: object

A decorator that creates a cached version of an instance method of a class.

NOTE:

For proper behavior, the method must be a pure function (no side effects). Arguments to the method must be hashable.

EXAMPLES:

sage: class Foo(object):
...       @cached_method
...       def f(self, t, x=2):
...           print 'computing'
...           return t**x
sage: a = Foo()

The example shows that the actual computation takes place only once, and that the result is identic for equivalent input:

sage: res = a.f(3, 2); res
computing
9
sage: a.f(t = 3, x = 2) is res
True
sage: a.f(3) is res
True
class sage.misc.cachefunc.CachedMethodCaller(cachedmethod, inst, cache=None, inst_in_key=False)

Bases: sage.misc.cachefunc.CachedFunction

Utility class that is used by CachedMethod to bind a cached method to an instance.

EXAMPLE:

sage: class A:
...    @cached_method
...    def bar(self,x):
...        return x^2
sage: a = A()
sage: a.bar
Cached version of <function bar at 0x...>
sage: type(a.bar)
<class 'sage.misc.cachefunc.CachedMethodCaller'>
sage: a.bar(2) is a.bar(x=2)
True
get_key(*args, **kwds)

Convert arguments to the key for this instance’s cache.

EXAMPLES:

sage: class Foo:
...       def __init__(self, x):
...           self._x = x
...       @cached_method
...       def f(self, y, z=0):
...           return self._x * y + z
...
sage: a = Foo(2)
sage: z = a.f(37)
sage: k = a.f.get_key(37); k
((37, 0), ())
sage: a.f.get_cache()[k] is z
True

Note that the method does not test whether there are too many arguments, or wrong argument names:

sage: a.f.get_key(1,2,3,x=4,y=5,z=6)
((1, 2, 3), (('x', 4), ('y', 5), ('z', 6)))

It does, however, take into account the different ways of providing named arguments, possibly with a default value:

sage: a.f.get_key(5)
((5, 0), ())
sage: a.f.get_key(y=5)
((5, 0), ())
sage: a.f.get_key(5,0)
((5, 0), ())
sage: a.f.get_key(5,z=0)
((5, 0), ())
sage: a.f.get_key(y=5,z=0)
((5, 0), ())
class sage.misc.cachefunc.CachedMethodPickle(inst, name)

This class helps to unpickle cached methods.

NOTE:

Since trac ticket #8611, a cached method is an attribute of the instance (provided that it has a __dict__). Hence, when pickling the instance, it would be attempted to pickle that attribute as well, but this is a problem, since functions can not be pickled, currently. Therefore, we replace the actual cached method by a place holder, that kills itself as soon as any attribute is requested. Then, the original cached attribute is reinstated.

EXAMPLE:

sage: R.<x, y, z> = PolynomialRing(QQ, 3)
sage: I = R*(x^3 + y^3 + z^3,x^4-y^4)
sage: I.groebner_basis()
[y^5*z^3 - 1/4*x^2*z^6 + 1/2*x*y*z^6 + 1/4*y^2*z^6, x^2*y*z^3 - x*y^2*z^3 + 2*y^3*z^3 + z^6, x*y^3 + y^4 + x*z^3, x^3 + y^3 + z^3]
sage: I.groebner_basis
Cached version of <function groebner_basis at 0x...>

We now pickle and unpickle the ideal. The cached method groebner_basis is replaced by a placeholder:

sage: J = loads(dumps(I))
sage: J.groebner_basis
Pickle of the cached method "groebner_basis"

But as soon as any other attribute is requested from the placeholder, it replaces itself by the cached method, and the entries of the cache are actually preserved:

sage: J.groebner_basis.is_in_cache()
True
sage: J.groebner_basis
Cached version of <function groebner_basis at 0x...>
sage: J.groebner_basis() == I.groebner_basis()
True

AUTHOR:

  • Simon King (2011-01)
class sage.misc.cachefunc.ClearCacheOnPickle

Bases: object

This class implements an appropriate __getstate__ method that clears the cache of the methods (see @cached_method) before passing them on to the caller, typically the pickle and copy modules.

The implemented __getstate__ method calls the __getstate__ methods of classes later in the method resolution order. Therefore, classes which wants this behaviour should inherit first from this one.

class sage.misc.cachefunc.DiskCachedFunction(f, dir, memory_cache=False)

Bases: sage.misc.cachefunc.CachedFunction

Works similar to CachedFunction, but instead, we keep the cache on disk (optionally, we keep it in memory too).

EXAMPLES:

sage: from sage.misc.cachefunc import DiskCachedFunction
sage: dir = tmp_dir()
sage: factor = DiskCachedFunction(factor, dir, memory_cache=True)
sage: f = factor(2775); f
3 * 5^2 * 37
sage: f is factor(2775)
True
class sage.misc.cachefunc.FileCache(dir, prefix='', memory_cache=False)

FileCache is a dictionary-like class which stores keys and values on disk. The keys take the form of a tuple (A,K)

  • A is a tuple of objects t where each t is an exact object which is uniquely identified by a short string.
  • K is a tuple of tuples (s,v) where s is a valid variable name and v is an exact object which is uniquely identified by a short string with letters [a-zA-Z0-9-._]

The primary use case is the DiskCachedFunction. If memory_cache == True, we maintain a cache of objects seen during this session in memory – but we don’t load them from disk until necessary. The keys and values are stored in a pair of files:

  • prefix-argstring.key.sobj contains the key only,
  • prefix-argstring.sobj contains the tuple (key,val)

where self[key] == val.

NOTE:

We assume that each FileCache lives in its own directory. Use extreme caution if you wish to break that assumption.

file_list()

Returns the list of files corresponding to self.

EXAMPLES:

sage: from sage.misc.cachefunc import FileCache
sage: dir = tmp_dir()
sage: FC = FileCache(dir, memory_cache = True, prefix='t')
sage: FC[((),())] = 1
sage: FC[((1,2),())] = 2
sage: FC[((1,),(('a',1),))] = 3
sage: for f in sorted(FC.file_list()): print f[len(dir):]
/t-.key.sobj
/t-.sobj
/t-1_2.key.sobj
/t-1_2.sobj
/t-a-1.1.key.sobj
/t-a-1.1.sobj
has_key(key)

Returns True if self[key] is defined and False otherwise.

EXAMPLES:

sage: from sage.misc.cachefunc import FileCache
sage: dir = tmp_dir() + '/'
sage: FC = FileCache(dir, memory_cache = False, prefix='foo')
sage: k = ((),(('a',1),))
sage: FC[k] = True
sage: FC.has_key(k)
True
sage: FC.has_key(((),()))
False
items()

Returns a list of tuples (k,v) where self[k] = v.

EXAMPLES:

sage: from sage.misc.cachefunc import FileCache
sage: dir = tmp_dir()
sage: FC = FileCache(dir, memory_cache = False)
sage: FC[((),())] = 1
sage: FC[((1,2),())] = 2
sage: FC[((1,),(('a',1),))] = 3
sage: I = FC.items()
sage: I.sort(); print I
[(((), ()), 1), (((1,), (('a', 1),)), 3), (((1, 2), ()), 2)]
keys()

Returns a list of keys k where self[k] is defined.

EXAMPLES:

sage: from sage.misc.cachefunc import FileCache
sage: dir = tmp_dir()
sage: FC = FileCache(dir, memory_cache = False)
sage: FC[((),())] = 1
sage: FC[((1,2),())] = 2
sage: FC[((1,),(('a',1),))] = 3
sage: K = FC.keys()
sage: K.sort(); print K
[((), ()), ((1,), (('a', 1),)), ((1, 2), ())]
values()

Returns a list of values that are stored in self.

EXAMPLES:

sage: from sage.misc.cachefunc import FileCache
sage: dir = tmp_dir()
sage: FC = FileCache(dir, memory_cache = False)
sage: FC[((),())] = 1
sage: FC[((1,2),())] = 2
sage: FC[((1,),(('a',1),))] = 3
sage: FC[((),(('a',1),))] = 4
sage: v = FC.values()
sage: v.sort(); print v
[1, 2, 3, 4]
sage.misc.cachefunc.cached_function

alias of CachedFunction

sage.misc.cachefunc.cached_in_parent_method

alias of CachedInParentMethod

sage.misc.cachefunc.cached_method

alias of CachedMethod

class sage.misc.cachefunc.disk_cached_function(dir, memory_cache=False)

Decorator for DiskCachedFunction.

EXAMPLES:

sage: dir = tmp_dir()
sage: @disk_cached_function(dir)
... def foo(x): return next_prime(2^x)%x
sage: x = foo(200);x
11
sage: @disk_cached_function(dir)
... def foo(x): return 1/x
sage: foo(200)
11
sage: foo.clear_cache()
sage: foo(200)
1/200

Previous topic

Abstract methods

Next topic

Function Mangling

This Page