Memoization (not memorization) is the process of remembering the
results of a computation for use later. (I think of it as “making a
memo” to look back on later.) Memoization is the core to any dynamic
programming implementation, and allows many simple algorithms to run
in linear or polynomial time when they would otherwise take an
exponential number of operations to complete. This is most obvious in
the typical recursive Fibonacci example. Consider the code:
[cc lang=”java”]
public class Fib{
public static void main(String[] args){
System.out.println("done: fib of "+args[0]+"="+
fib(Integer.parseInt(args[0])));
}
public static int fib(int n){
int rval = 1;
if (n >= 2){
rval = fib(n - 1) + fib(n - 2);
}
System.out.println("fib("+n+") = "+rval);
return rval;
}
}[/cc]
This is a straight-forward recursive implementation of fib. When run
with n=4, we see this:
[cc lang=”bash”]
$ javac Fib.java && java Fib 4
fib(1) = 1
fib(0) = 1
fib(2) = 2
fib(1) = 1
fib(3) = 3
fib(1) = 1
fib(0) = 1
fib(2) = 2
fib(4) = 5
done: fib of 4=5
[/cc]
9 invocations of fib(n), but only 5 unique invocations. Lets
memoize the results, and try this again:
[cc lang=”bash”]
$ javac Fib.java && java Fib 4
fib(1) = 1
fib(0) = 1
fib(2) = 2
fib(3) = 3
fib(4) = 5
done: fib of 4=5
[/cc]
Much better – 5 invocations, 5 unique sets of parameters.
Here’s the source with memoization:
[cc lang=”java”]
public class Fib{
static Map<Integer, Integer> memos = new HashMap(); // new
public static void main(String[] args){
System.out.println("done: fib of "+args[0]+"="+
fib(Integer.parseInt(args[0])));
}
public static int fib(int n){
if (memos.containsKey(n)) // new
return memos.get(n); // new
int rval = 1;
if (n >= 2) {
rval = fib(n - 1) + fib(n - 2);
}
System.out.println("fib("+n+") = "+rval);
memos.put(n, rval); // new
return rval;
}
}[/cc]
Notice that we only needed to add 4 new lines of code in order to
memoize the results. When fib(n) is called, it simply checks to see
if it has previously been called with n, and if so, that result is
used again. If the parameter has never been seen before, the method
continues as normal, storing the computed result before returning.
Memoization turns this naive (and exponential) implementation of fib(n)
into an efficient (linear) operation.
Memoization in the real world
So, (un?)fortunately we don’t spend all day implementing cool new ways
of computing ever increasing entries of the fibinocci sequence – how
can memoization be put to use? After all, many algorithms are already
implemented in some fairly optimal fashion by the language APIs, and
you’d be a fool not to use those implementations. What opportunity
will you have to memoize functions?
It turns out that you can memoize anything, as long as the function
is pure with respect to the memos (meaning: the function doesn’t depend on any thing that is not used to key the hash of memos). If the function is not pure, then you can still use memoization, but either the memo hash must key on all the state and parameters that can affect the results of the function. On the other hand, if f depends on some state that changes very rarely, then it may make more sense to simply discard all the stored memos each time that aspect of state is altered.
Memoization is extremely handy when you have very common operations that are
fairly expensive. I recently needed to optimize some code that
compares strings based on the case-insensitive stems of the words,
with stopwords removed. So the strings “he wanted an apple” and “he
wants apples” should be equal. (“an” is a stopword, and ignored)
This meant doing many, many calls to a string stemmer, each of which
is a fairly expensive operation. Fortunately, hashing strings as
extremely cheap (on the order of 1/4th the time it took to stem a
string of the same length), and I had plenty of memory to store the
parameters and the results in a Map. Adding memos to
the two primary time-hoggers (the stemmer and a tokenizer) cut the
execution time of the application down from 2 hours to just over 7
minutes.
Summary
You can memoize any function that only depends on it’s parameters and
constant state (or near-constant state – just don’t forget to discard your
memos when the state changes!). If the function is invoked multiple
times you will probably see a performance improvement.
If you need to memoize a function with multiple arguments, then you
just need to nest Maps, or create a unique key by combining the
parameters in some way.
Memoization is an extremely easy way to improve performance under
certain circumstances, particularly if you have a solid grasp on when
state changes outside of your methods / functions, or program in a
functional style. It can be memory intensive, however. If the
results of your functions are large, or maintain references to large
objects, then memoization may penalize performance if you run out of
memory and have to make use of swap space.
