Memoize 1.01

Memoize - Make functions faster by trading space for time.

SYNOPSIS

# This is the documentation for Memoize 1.01
use Memoize;
memoize(slow_function);
slow_function(arguments); # Is faster than it was before

This is normally all you need to know. However, many options are available:

memoize(function, options...);

Options include:

NORMALIZER => function
INSTALL => new_name

SCALAR_CACHE => MEMORY
SCALAR_CACHE => [HASH, %cache_hash ]
SCALAR_CACHE => FAULT
SCALAR_CACHE => MERGE

LIST_CACHE => MEMORY
LIST_CACHE => [HASH, %cache_hash ]
LIST_CACHE => FAULT
LIST_CACHE => MERGE

`Memoizing a function makes it faster by trading space for time. It does this by caching the return values of the function in a table. If you call the function again with the same arguments, memoize jumps in and gives you the value out of the table, instead of letting the function compute the value all over again.

Here is an extreme example. Consider the Fibonacci sequence, defined by the following function:

# Compute Fibonacci numbers
sub fib {
my $n = shift;
return $n if $n < 2;
fib($n-1) + fib($n-2);
}

This function is very slow. Why? To compute fib(14), it first wants to compute fib(13) and fib(12), and add the results. But to compute fib(13), it first has to compute fib(12) and fib(11), and then it comes back and computes fib(12) all over again even though the answer is the same. And both of the times that it wants to compute fib(12), it has to compute fib(11) from scratch, and then it has to do it again each time it wants to compute fib(13). This function does so much recomputing of old results that it takes a really long time to run---fib(14) makes 1,200 extra recursive calls to itself, to compute and recompute things that it already computed.

This function is a good candidate for memoization. If you memoize the `fib function above, it will compute fib(14) exactly once, the first time it needs to, and then save the result in a table. Then if you ask for fib(14) again, it gives you the result out of the table. While computing fib(14), instead of computing fib(12) twice, it does it once; the second time it needs the value it gets it from the table. It doesnt compute fib(11) four times; it computes it once, getting it from the table the next three times. Instead of making 1,200 recursive calls to `fib, it makes 15. This makes the function about 150 times faster.

You could do the memoization yourself, by rewriting the function, like this:

# Compute Fibonacci numbers, memoized version
{ my @fib;
sub fib {
my $n = shift;
return $fib[$n] if defined $fib[$n];
return $fib[$n] = $n if $n < 2;
$fib[$n] = fib($n-1) + fib($n-2);
}
}

Or you could use this module, like this:

use Memoize;
memoize(fib);

# Rest of the fib function just like the original version.

This makes it easy to turn memoizing on and off.

Heres an even simpler example: I wrote a simple ray tracer; the program would look in a certain direction, figure out what it was looking at, and then convert the `color value (typically a string like `red) of that object to a red, green, and blue pixel value, like this:

for ($direction = 0; $direction < 300; $direction++) {
# Figure out which object is in direction $direction
$color = $object->{color};
($r, $g, $b) = @{&ColorToRGB($color)};
...
}

Since there are relatively few objects in a picture, there are only a few colors, which get looked up over and over again. Memoizing ColorToRGB sped up the program by several percent.