MAN page from Mandrake Other perl-Memoize-0.47-1.i386.rpm

Memoize

Section: User Contributed Perl Documentation (3)
Updated: perl 5.004, patch 04
Index

NAME

Memoize - Make your functions faster by trading space for time

SYNOPSIS

 use Memoize; memoize('slow_function'); slow_function(arguments);    # Is faster than it was before

DESCRIPTION

`Memoizing' a function makes it faster by trading space for time. Itdoes this by cacheing the return values of the function in a table.If you call the function again with the same arguments, memoizejmups in and gives you the value out of the table, instead of lettingthe function compute the value all over again.

Here is an extreme example. Consider the Fibonacci sequence, definedby 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 wantsto compute fib(13) and fib(12), and add the results. But to computefib(13), it first has to compute fib(12) and fib(11), and then itcomes back and computes fib(12) all over again even though the answeris 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 itagain each time it wants to compute fib(13). This function does somuch recomputing of old results that it takes a really long time torun---fib(14) makes 1,200 extra recursive calls to itself, to computeand 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 firsttime it needs to, and then save the result in a table. Then if youask for fib(14) again, it gives you the result out of the table.While computing fib(14), instead of computing fib(12) twice, it doesit once; the second time it needs the value it gets it from the table.It doesn't compute fib(11) four times; it computes it once, getting itfrom the table the next three times. Instead of making 1,200recursive calls to `fib', it makes 15. This makes the function about150 times faster.

You could do the memoization yourself, by rewriting the function, likethis:

        # 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.

Here's an even simpler example: I wrote a simple ray tracer; theprogram would look in a certain direction, figure out what it waslooking at, and then convert the `color' value (typically a stringlike `red') of that object to a red, green, and blue pixel value, likethis:

    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 afew colors, which get looked up over and over again. MemoizingColorToRGB speeded up the program by several percent.

DETAILS

This module exports exactly one function, memoize. The rest of thefunctions in this package are None of Your Business.

You should say

        memoize(function)

where function is the name of the function you want to memoize, ora reference to it. memoize returns a reference to the new,memoized version of the function, or undef on a non-fatal error.At present, there are no non-fatal errors, but there might be some inthe future.

If function was the name of a function, then memoize hides theold version and installs the new memoized version under the old name,so that &function(...) actually invokes the memoized version.

OPTIONS

There are some optional options you can pass to memoize to changethe way it behaves a little. To supply options, invoke memoizelike this:

        memoize(function, NORMALIZER => function,                          INSTALL => newname,                          SCALAR_CACHE => option,                          LIST_CACHE => option                         );

Each of these options is optional; you can include some, all, or noneof them.

INSTALL

If you supply a function name with INSTALL, memoize will installthe new, memoized version of the function under the name you give.For example,

        memoize('fib', INSTALL => 'fastfib')

installs the memoized version of fib as fastfib; without theINSTALL option it would have replaced the old fib with thememoized version.

To prevent memoize from installing the memoized version anywhere, useINSTALL => undef.

NORMALIZER

Suppose your function looks like this:

        # Typical call: f('aha!', A => 11, B => 12);        sub f {          my $a = shift;          my %hash = @_;          $hash{B} ||= 2;  # B defaults to 2          $hash{C} ||= 7;  # C defaults to 7

          # Do something with $a, %hash        }

Now, the following calls to your function are all completely equivalent:

        f(OUCH);        f(OUCH, B => 2);        f(OUCH, C => 7);        f(OUCH, B => 2, C => 7);        f(OUCH, C => 7, B => 2);        (etc.)

However, unless you tell Memoize that these calls are equivalent,it will not know that, and it will compute the values for theseinvocations of your function separately, and store them separately.

To prevent this, supply a NORMALIZER function that turns theprogram arguments into a string in a way that equivalent argumentsturn into the same string. A NORMALIZER function for f abovemight look like this:

        sub normalize_f {          my $a = shift;          my %hash = @_;          $hash{B} ||= 2;          $hash{C} ||= 7;

          join($;, $a, map ($_ => $hash{$_}) sort keys %hash);        }

Each of the argument lists above comes out of the normalize_ffunction looking exactly the same, like this:

        OUCH^\B^\2^\C^\7

You would tell Memoize to use this normalizer this way:

        memoize('f', NORMALIZER => 'normalize_f');

memoize knows that if the normalized version of the arguments isthe same for two argument lists, then it can safely look up the valuethat it computed for one argument list and return it as the result ofcalling the function with the other argument list, even if theargument lists look different.

The default normalizer just concatenates the arguments with $; inbetween. This always works correctly for functions with only oneargument, and also when the arguments never contain $; (which isnormally character #28, control-\. ) However, it can confuse certainargument lists:

        normalizer("a\034", "b")        normalizer("a", "\034b")        normalizer("a\034\034b")

for example.

The calling context of the function (scalar or list context) ispropagated to the normalizer. This means that if the memoizedfunction will treat its arguments differently in list context than itwould in scalar context, you can have the normalizer function selectits behavior based on the results of wantarray. Even if called ina list context, a normalizer should still return a single string.

SCALAR_CACHE, LIST_CACHE

Normally, Memoize caches your function's return values into anordinary Perl hash variable. However, you might like to have thevalues cached on the disk, so that they persist from one run of yourprogram to the next, or you might like to associate some otherinteresting semantics with the cached values.

There's a slight complication under the hood of Memoize: There areactually two caches, one for scalar values and one for list values.When your function is called in scalar context, its return value iscached in one hash, and when your function is called in list context,its value is cached in the other hash. You can control the cachingbehavior of both contexts independently with these options.

The argument to LIST_CACHE or SCALAR_CACHE must either be one ofthe following four strings:

        MEMORY        TIE        FAULT        MERGE

or else it must be a reference to a list whose first element is one ofthese four strings, such as [TIE, arguments...].

MEMORY

MEMORY means that return values from the function will be cached inan ordinary Perl hash variable. The hash variable will not persistafter the program exits. This is the default.

TIE

TIE means that the function's return values will be cached in atied hash. A tied hash can have any semantics at all. It istypically tied to an on-disk database, so that cached values arestored in the database and retrieved from it again when needed, andthe disk file typically persists after your pogram has exited.

If TIE is specified as the first element of a list, the remaininglist elements are taken as arguments to the tie call that sets upthe tied hash. For example,

        SCALAR_CACHE => [TIE, DB_File, $filename, O_RDWR | O_CREAT, 0666]

says to tie the hash into the DB_File package, and to pass the$filename, O_RDWR | O_CREAT, and 0666 arguments to the tiecall. This has the effect of storing the cache in a DB_Filedatabase whose name is in $filename.

Other typical uses of TIE:

        LIST_CACHE => [TIE, GDBM_File, $filename, O_RDWR | O_CREAT, 0666]        SCALAR_CACHE => [TIE, MLDBM, DB_File, $filename, O_RDWR|O_CREAT, 0666]        LIST_CACHE => [TIE, My_Package, $tablename, $key_field, $val_field]

This last might tie the cache hash to a package that you wroteyourself that stores the cache in a SQL-accessible database.A useful use of this feature: You can construct a batch program thatruns in the background and populates the memo table, and then when youcome to run your real program the memoized function will bescreamingly fast because all its results have been precomputed.

FAULT

FAULT means that you never expect to call the function in scalar(or list) context, and that if Memoize detects such a call, itshould abort the program. The error message is one of

        `foo' function called in forbidden list context at line ...        `foo' function called in forbidden scalar context at line ...

MERGE

MERGE normally means the function does not distinguish between listand sclar context, and that return values in both contexts should bestored together. LIST_CACHE => MERGE means that list contextreturn values should be stored in the same hash that is used forscalar context returns, and SCALAR_CACHE => MERGE means thesame, mutatis mutandis. It is an error to specify MERGE for both,but it probably does something useful.

Consider this function:

        sub pi { 3; }

Normally, the following code will result in two calls to pi:

    $x = pi();    ($y) = pi();    $z = pi();

The first call caches the value 3 in the scalar cache; the secondcaches the list (3) in the list cache. The third call doesn't callthe real pi function; it gets the value from the scalar cache.

Obviously, the second call to pi is a waste of time, and storingits return value is a waste of space. Specifying LIST_CACHE=> MERGE will make memoize use the same cache for scalar andlist context return values, so that the second call uses the scalarcache that was populated by the first call. pi ends up beingcvalled only once, and both subsequent calls return 3 from thecache, regardless of the calling context.

Another use for MERGE is when you want both kinds of return valuesstored in the same disk file; this saves you from having to deal withtwo disk files instead of one. You can use a normalizer function tokeep the two sets of return values separate. For example:

        memoize 'myfunc',          NORMALIZER => 'n',          SCALAR_CACHE => [TIE, MLDBM, DB_File, $filename, ...],          LIST_CACHE => MERGE,        ;

        sub n {          my $context = wantarray() ? 'L' : 'S';          # ... now compute the hash key from the arguments ...          $hashkey = "$context:$hashkey";        }

This normalizer function will store scalar context return values inthe disk file under keys that begin with S:, and list contextreturn values under keys that begin with L:.

OTHER FUNCTION

There's an unmemoize function that you can import if you want to.If you use it, please let me know what it was good for, since I canonly think of very limited uses for it and was considering leaving itout altogether.

It accepts a reference to, or the name of a previously memoizedfunction, and undoes whatever it did to provide the memoized versionin the first place, including making the name refer to the unmemoizedversion if appropriate. It returns a reference to the unmemoizedversion of the function.

If you ask it to unmemoize a function that was never memoized, itcroaks.

CAVEATS

Memoization is not a cure-all:

•

Do not memoize a function whose behavior depends on programstate other than its own arguments, such as global variables, the timeof day, or file input. These functions will not produce correctresults when memoized. For a particularly easy example:

        sub f {          time;        }

This function takes no arguments, and as far as Memoize isconcerned, it always returns the same result. Memoize is wrong, ofcourse, and the memoized version of this function will call time onceto get the current time, and it will return that same timeevery time you call it after that.

•

Do not memoize a function with side effects.

        sub f {          my ($a, $b) = @_;          my $s = $a + $b;          print "$a + $b = $s.\n";        }

This function accepts two arguments, adds them, and prints their sum.Its return value is the numuber of characters it printed, but youprobably didn't care about that. But Memoize doesn't understandthat. If you memoize this function, you will get the result youexpect the first time you ask it to print the sum of 2 and 3, butsubsequent calls will return the number 11 (the return value ofprint) without actually printing anything.

•

Do not memoize a function that returns a data structure that ismodified by its caller.

Consider these functions: getusers returns a list of users somehow,and then main throws away the first user on the list and prints therest:

        sub main {          my $userlist = getusers();          shift @$userlist;          foreach $u (@$userlist) {            print "User $u\n";          }        }

        sub getusers {          my @users;          # Do something to get a list of users;          \@users;  # Return reference to list.        }

If you memoize getusers here, it will work right exactly once. Thereference to the users list will be stored in the memo table. mainwill discard the first element from the referenced list. The nexttime you invoke main, Memoize will not call getusers; it willjust return the same reference to the same list it got last time. Butthis time the list has already had its head removed; main willerroneously remove another element from it. The list will get shorterand shorter every time you call main.

PERSISTENT CACHE SUPPORT

You can tie the cache tables to any sort of tied hash that you wantto, as long as it supports TIEHASH, FETCH, STORE, andEXISTS. For example,

        memoize 'function', SCALAR_CACHE =>                             [TIE, GDBM_File, $filename, O_RDWR|O_CREAT, 0666];

works just fine. For some storage methods, you need a little glue.

SDBM_File doesn't supply an EXISTS method, so included in thispackage is a glue module called Memoize::SDBM_File which doesprovide one. Use this instead of plain SDBM_File to store yourcache table on disk in an SDBM_File database:

        memoize 'function',                 SCALAR_CACHE =>                 [TIE, Memoize::SDBM_File, $filename, O_RDWR|O_CREAT, 0666];

NDBM_File has the same problem and the same solution.

Storable isn't a tied hash class at all. You can use it to store ahash to disk and retrieve it again, but yu can't modify the hash whileit's on the disk. So if you want to store your cache table in aStorable database, use Memoize::Storable, which puts a hashlikefront-end onto Storable. The hash table is actually kept inmemory, and is loaded from your Storable file at the time youmemoize the function, and stored back at the time you unmemoize thefunction (or when your program exits):

        memoize 'function',                 SCALAR_CACHE => [TIE, Memoize::Storable, $filename];

        memoize 'function',                 SCALAR_CACHE => [TIE, Memoize::Storable, $filename, 'nstore'];

Include the `nstore' option to have the Storable database writtenin `network order'. (See the Storable manpage for moer details about this.)

MY BUGS

Needs a better test suite, especially for the tied stuff.That is why the version number is 0.46 instead of 0.50.

MAILING LIST

To join a very low-traffic mailing list for announcements aboutMemoize, send an empty note to mjd-perl-memoize-requestAATTplover.com.

AUTHOR

This document was created byman2html,using the manual pages.