Macaulay2 » Documentation
Packages » Macaulay2Doc » The Macaulay2 language » caching computation results » memoize
next | previous | forward | backward | up | index | toc

# memoize -- record results of function evaluation for future use

## 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 1.13187s (cpu); 0.756026s (thread); 0s (gc)

    o2 = 514229

    i3 : fib = memoize fib

    o3 = fib

    o3 : FunctionClosure

    i4 : time fib 28
     -- used 7.213e-05s (cpu); 7.177e-05s (thread); 0s (gc)

    o4 = 514229

    i5 : time fib 28
     -- used 2.49e-06s (cpu); 2.33e-06s (thread); 0s (gc)

    o5 = 514229

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.

Alternatively, values can be provided after defining the memoized function using the syntax f x = v. A slightly more efficient implementation of the above would be

    i6 : fib = memoize( n -> fib(n-1) + fib(n-2) )

    o6 = fib

    o6 : FunctionClosure

    i7 : fib 0 = fib 1 = 1;

    i8 : fib 28

    o8 = 514229

The function memoize operates by constructing a MutableHashTable, in which the arguments are used as keys for accessing the return value of the function. This mutable hash table can be obtained using the function memoizeValues, as follows.

    i9 : peek memoizeValues fib

    o9 = MutableHashTable{0 => 1      }
                          1 => 1
                          2 => 2
                          3 => 3
                          4 => 5
                          5 => 8
                          6 => 13
                          7 => 21
                          8 => 34
                          9 => 55
                          10 => 89
                          11 => 144
                          12 => 233
                          13 => 377
                          14 => 610
                          15 => 987
                          16 => 1597
                          17 => 2584
                          18 => 4181
                          19 => 6765
                          20 => 10946
                          21 => 17711
                          22 => 28657
                          23 => 46368
                          24 => 75025
                          25 => 121393
                          26 => 196418
                          27 => 317811
                          28 => 514229

That hash table can be replaced by an empty one with the function memoizeClear.

    i10 : memoizeClear fib

    i11 : peek memoizeValues fib

    o11 = MutableHashTable{}

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.

## Ways to use memoize:

- `memoize(Function)`
- `memoize(Function,List)`

## For the programmer

The object memoize is a method function.

The source of this document is in /build/macaulay2-88fgJW/macaulay2-1.25.11+ds/M2/Macaulay2/packages/Macaulay2Doc/ov_repl.m2:708:0.