External Memoization Using Modules
This worksheet demonstrates a technique for building robust memoized procedures using modules and other techniques. This worksheet is referenced in the help topic on efficiency hints, and goes into further detail about the caching and memoization techniques mentioned there.
Memoization of a procedure is a process by which previously computed values are stored somewhere and, whenever a computation is to be repeated, the stored valued is looked up and returned instead of repeating the entire (typically expensive) computation.
Maple already provides automatic memoization by means of the "remember" option that may be specified for procedures. A procedure with option remember has, as part of its internal data structure, a table in which previously computed values are stored. Whenever the procedure is called, Maple examines the remember table (if one exists) to determine whether the procedure has been called before with the same arguments and therefore has a stored value. If a stored value is found, then it is returned; otherwise, the computation is performed normally, and the computed value is stored in the remember table of the procedure.
restart:
Caching
Caching is an optimization technique that can be used in situations in which you do not want to incur the storage overhead of option remember, but would like to store the last (or last few) computed results. This technique is advantageous when you expect a procedure to be called repeatedly with the same inputs
Instead of storing all results in a table when they are computed, save only the most recent argument sequence and computed result. The simplest way to do this is to store these values in a pair of global variables. The following procedure, which caches the most recently computed determinant, illustrates this straightforward mechanism.
CachedDet := proc( m )
global cdet_args, cdet_result;
local last_args, last_result;
last_args, last_result := cdet_args, cdet_result;
if [ last_args ] = [ args ] then
last_result
else
try
last_args := args;
last_result := LinearAlgebra:-Determinant( args )
catch:
error
end try;
cdet_args := last_args;
cdet_result := last_result
end if
end proc:
M := LinearAlgebra:-RandomMatrix( 50, 50, 'outputoptions' = [ 'datatype' = 'integer' ] ):
time( CachedDet( M ) );
2.980
time( seq( CachedDet( M ), i = 1 .. 100 ) );
0.010
The principal difficulty with this technique is that is relies on global variables, which should be avoided whenever possible. Essentially the same mechanism can be used if the cache variables are instead stored as local variables of a module that exports the caching wrapper routine. The cache variables (detargs and detresult below) must be local to the module to prevent "tampering," and to avoid colliding with other globals.
DetCache := module()
export cached_det;
local detargs, detresult;
cached_det := proc( m )
last_args, last_result := detargs, detresult;
detargs := last_args;
detresult := last_result
end proc;
end module:
CachedDet := DetCache:-cached_det;
CachedDet:=cached_det
time( seq( CachedDet( M ), i = 1 .. 10 ) );
0.
You can use Maple's dynamic nature to create a procedure that automates the creation of cached versions of procedures. This allows you to apply the technique to already coded routines, without having to recode them. Here, we develop a Maple procedure called CachedProc that, when applied to a Maple procedure, returns a new procedure that employs the caching optimization.
CachedProc := proc( p )
local m;
# Build the caching module
m := module()
local theArgs, theResult;
export cachedProc;
# Create the optimised procedure
cachedProc := proc()
local lastArgs, lastResult;
lastArgs := theArgs; lastResult := theResult;
if [ lastArgs ] = [ args ] then
lastResult
lastArgs := args;
lastResult := p( args )
theArgs := lastArgs;
theResult := lastResult
end proc
end module;
eval( m:-cachedProc )
cint := CachedProc( radnormal@int );
cint:=proclocallastArgs,lastResult;lastArgs:=theArgs;lastResult:=theResult;iflastArgs=argsthenlastResultelsetrylastArgs:=args;lastResult:=radnormal@intargscatch:errorend try;theArgs:=lastArgs;theResult:=lastResultend ifend proc
time( cint( sin(x^4), x ) );
0.950
The sort of computation for which this kind of optimization is suitable is illustrated by the following example. Here, a list of 1000 entries is sorted, and a procedure is mapped onto the list. When the list contains many duplicated elements, caching can reduce the time required.
r := rand(1..10):
L := sort( [seq(expand(ChebyshevT(r(),x)),i=1..1000)] ):
nops( L ), nops( convert( L, 'set' ) );
1000,10
time( map( CachedProc( radnormal@int ), L, x ) );
0.189
time( map( radnormal@int, L, x ) );
1.500
evalf( % / %% );
7.936507936
Remembering Extra Information
The remember option cannot always be used on a procedure. The result of a computation may depend on the values of global or environment variables. A procedure may also return a result in a parameter passed as a name. (For details, see Procedure parameter definition and type checking.) The built-in procedure evalf has a specially managed remember table that, in addition to storing the arguments to a call, stores the current value of the environment variable Digits, upon which the results of evalf depend. This kind of facility is not provided by the remember option.
You can implement your own procedures that store extra information, such as the values of global or environment variables, by using modules.
Here, the procedure f depends on the global variable t. The results of calling it with the same argument may differ if the value of t at the time of the call is different.
f := proc( x )
global t;
x + t
t := 2:
f( 2 );
4
t := 3;
t:=3
5
For procedures such as this, the remember option is not valid.
f := proc( x ) global t; option remember; x + t end proc:
t := 0:
2
t := 3:
To take advantage of memoizing optimizations for procedures that have "external" dependencies, you can use a module to provide a "safe" environment in which to store previously computed results, and which stores--in addition to the argument sequence--all required external information. An implementation of a memoized variant of the procedure f above follows. This technique uses a local variable of the module memo_f to hold a table in which the values that have been computed are stored. The values are keyed on both the argument x and the global variable t.
memo_f := module()
export f;
local memory; # table in which to store results
if assigned( memory[ t, x ] ) then
memory[ t, x ]
memory[ t, x ] := x + t
f := memo_f:-f;
f:=f
t := 0;
t:=0
An alternative technique is to use a helper procedure that takes extra arguments (in this case, just one) that does not depend on any external state and to which the remember option may validly be applied. The procedure of interest can then call the helper procedure, passing any required external values as extra arguments.
Here, for example, the procedure f is written to call the helper procedure remf, which takes two arguments and to which the remember option may validly be applied. It passes the value of the global variable t as a second parameter to remf.
remf := proc( a, b )
option remember;
a + b
global remf, t;
remf( x, t )
This technique also works well, but suffers the disadvantage that the helper procedure remf, and thus its remember table, are globally accessible and subject to "tampering."
Performing Selective Memoization
Another case in which special-purpose memoization code may be useful is for selective memoization, in which only certain among the previously computed values are to be stored. For example, there may be two cases in a computation, one of which is expensive. Results that were obtained by expensive computation can be stored, while those that are able to be computed cheaply need not be.
pgcd := proc( a, b, p )
if type( [ a, b ], '[ zppoly, zppoly ]' ) then
modp1( Gcd( a, b ), p )
modp( Gcd( a, b ), p )
p := 11:
pgcd( 13, 4, p );
1
a := modp1( ConvertIn( 1 - (p-1)*T + T^2, T ), p ):
b := modp1( ConvertIn( 1 - (p-1)*T - T^2, T ), p ):
g := pgcd( a, b, p ):
type( g, 'zppoly' );
true
#store the results of polynomial gcd's but not integer gcd's pgcd_memo := module()
local memory;
export pgcd;
memory := table();
memory[ a, b, p ] := modp1( Gcd( a, b ), p )
pgcd := pgcd_memo:-pgcd;
pgcd:=pgcd
pgcd( 15, 13, p );
pgcd( a, b, p );
1 mod 11
Return to Index for Example Worksheets
Download Help Document
