Description
memoize f -- produces, from a function
f, a new function that behaves the same as
f, but remembers previous answers to be provided the next time the same arguments are presented.
i1 : fib = n -> if n <= 1 then 1 else fib(n-1) + fib(n-2)
o1 = fib
o1 : FunctionClosure
|
i2 : time fib 28
-- used 3.62514 seconds
o2 = 514229
|
i3 : fib = memoize fib
o3 = fib
o3 : FunctionClosure
|
i4 : time fib 28
-- used 0.000086673 seconds
o4 = 514229
|
i5 : time fib 28
-- used 2.28e-6 seconds
o5 = 514229
|
The function
memoize operates by constructing a
MutableHashTable in which the argument sequences are used as keys for accessing the return value of the function.
An optional second argument to memoize provides a list of initial values, each of the form
x => v, where
v is the value to be provided for the argument
x.
Warning: the new function created by
memoize will save references to all arguments and values it encounters, and this will often prevent those arguments and values from being garbage-collected as soon as they might have been. If the arguments are implemented as mutable hash tables (modules, matrices and rings are implemented this way) then a viable strategy is to stash computed results in the arguments themselves. See also
CacheTable.