~ubuntu-branches/ubuntu/intrepid/perl-doc-html/intrepid

      <h2>Links:</h2>

      <ul>

        <li><a href="http://search.cpan.org">CPAN</a></li>

        <li><a href="http://www.perl.com">Perl.com</a></li>

        <li><a href="http://www.pm.org">Perl Mongers</a></li>

        <li><a href="http://www.perlmonks.org">Perl Monks</a></li>

        <li><a href="http://planet.perl.org">Planet Perl</a></li>

      <ul>

        <li>Site maintained by<br><a href="http://perl.jonallen.info">Jon Allen</a>

            (<a href="http://perl.jonallen.info">JJ</a>)</li>

        <li class="spaced">See the <a href="http://perl.jonallen.info/projects/perldoc">project page</a> for

        more details</li>

      </ul>

    <div id="centerContent">

      <div id="contentHeader">

        <div id="contentHeaderLeft"><a href="#" onClick="showLeft()">Show navigation</a></div>

        <div id="contentHeaderRight"><a href="#" onClick="showRight()">Show toolbar</a></div>

      </div>

      <div id="breadCrumbs"><a href="index.html">Home</a> &gt; <a href="index-modules-A.html">Core modules</a> &gt; <a href="index-modules-M.html">M</a> &gt; Memoize</div>

      <script language="JavaScript">fromSearch();</script>

</a></ul><li><a href="#CAVEATS">CAVEATS</a><li><a href="#PERSISTENT-CACHE-SUPPORT">PERSISTENT CACHE SUPPORT</a><li><a href="#EXPIRATION-SUPPORT">EXPIRATION SUPPORT</a><li><a href="#BUGS">BUGS</a><li><a href="#MAILING-LIST">MAILING LIST</a><li><a href="#AUTHOR">AUTHOR</a><li><a href="#COPYRIGHT-AND-LICENSE">COPYRIGHT AND LICENSE</a><li><a href="#THANK-YOU">THANK YOU</a></ul><a name="NAME"></a><h1>NAME</h1>

<p>Memoize - Make functions faster by trading space for time</p>

<a name="SYNOPSIS"></a><h1>SYNOPSIS</h1>

<pre class="verbatim">        <span class="c"># This is the documentation for Memoize 1.01</span>

        <span class="i">memoize</span><span class="s">(</span><span class="q">&#39;slow_function&#39;</span><span class="s">)</span><span class="sc">;</span>

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

<p>Options include:</p>

<a name="DESCRIPTION"></a><h1>DESCRIPTION</h1>

<p>`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.

 

jumps in and gives you the value out of the table, instead of letting

the function compute the value all over again.</p>

          <span class="s">}</span>

        <span class="s">}</span></pre>

<p>Or you could use this module, like this:</p>

        <span class="i">memoize</span><span class="s">(</span><span class="q">&#39;fib&#39;</span><span class="s">)</span><span class="sc">;</span></pre>

<pre class="verbatim">  <span class="c"># Rest of the fib function just like the original version.</span></pre>

<p>This makes it easy to turn memoizing on and off.</p>

this:</p>

<pre class="verbatim">    for <span class="s">(</span><span class="i">$direction</span> = <span class="n">0</span><span class="sc">;</span> <span class="i">$direction</span> &lt; <span class="n">300</span><span class="sc">;</span> <span class="i">$direction</span>++<span class="s">)</span> <span class="s">{</span>

      <span class="c"># Figure out which object is in direction $direction</span>

      <span class="s">(</span><span class="i">$r</span><span class="cm">,</span> <span class="i">$g</span><span class="cm">,</span> <span class="i">$b</span><span class="s">)</span> = <span class="i">@</span>{<span class="i">&amp;ColorToRGB</span><span class="s">(</span><span class="i">$color</span><span class="s">)</span>}<span class="sc">;</span>

      ...

    <span class="s">}</span></pre>

<p>Since there are relatively few objects in a picture, there are only a

few colors, which get looked up over and over again.  Memoizing

 sped up the program by several percent.</p>

<a name="DETAILS"></a><h1>DETAILS</h1>

.  The rest of the

functions in this package are None of Your Business.</p>

<p>You should say</p>

 is the name of the function you want to memoize, or

 returns a reference to the new,

memoized version of the function, or <code class="inline"><a class="l_k" href="functions/undef.html">undef</a></code> on a non-fatal error.

At present, there are no non-fatal errors, but there might be some in

the future.</p>

 hides the

old version and installs the new memoized version under the old name,

so that <code class="inline"><span class="i">&amp;function</span><span class="s">(</span>...<span class="s">)</span></code>

 actually invokes the memoized version.</p>

<a name="OPTIONS"></a><h1>OPTIONS</h1>

 to change

 

like this:</p>

                         <span class="s">)</span><span class="sc">;</span></pre>

<p>Each of these options is optional; you can include some, all, or none

of them.</p>

<a name="INSTALL"></a><h2>INSTALL</h2>

, memoize will install

the new, memoized version of the function under the name you give.

; without the

 with the

 from installing the memoized version anywhere, use

.</p>

<a name="NORMALIZER"></a><h2>NORMALIZER</h2>

<p>Suppose your function looks like this:</p>

          $hash{B} ||= 2;  # B defaults to 2

          $hash{C} ||= 7;  # C defaults to 7</pre><pre class="verbatim">          # Do something with $a, %hash

        }</pre><p>Now, the following calls to your function are all completely equivalent:</p>

it will not know that, and it will compute the values for these

invocations of your function separately, and store them separately.</p>

 function that turns the

program arguments into a string in a way that equivalent arguments

 above

might look like this:</p>

<pre class="verbatim">  sub normalize_f {

          my %hash = @_;

          $hash{B} ||= 2;

          $hash{C} ||= 7;</pre><pre class="verbatim">     join(',', $a, map ($_ =&gt; $hash{$_}) sort keys %hash);

 

function looking exactly the same, like this:</p>

 knows that if the normalized version of the arguments is

the same for two argument lists, then it can safely look up the value

that it computed for one argument list and return it as the result of

<p>Since hash keys are strings, the default normalizer will not

distinguish between <code class="inline"><a class="l_k" href="functions/undef.html">undef</a></code> and the empty string.  It also won't work

when the function's arguments are references.  For example, consider a

 which gets two arguments: A number, and a reference to

an array of numbers:</p>

<pre class="verbatim">  <span class="i">g</span><span class="s">(</span><span class="n">13</span><span class="cm">,</span> <span class="s">[</span><span class="n">1</span><span class="cm">,</span><span class="n">2</span><span class="cm">,</span><span class="n">3</span><span class="cm">,</span><span class="n">4</span><span class="cm">,</span><span class="n">5</span><span class="cm">,</span><span class="n">6</span><span class="cm">,</span><span class="n">7</span><span class="s">]</span><span class="s">)</span><span class="sc">;</span></pre>

<code class="inline"><span class="q">&quot;13\034ARRAY(0x436c1f)&quot;</span></code>

.  That would be all right, except that a

subsequent array of numbers might be stored at a different location

will think that the arguments are different, even though they are

equivalent.  In this case, a normalizer like this is appropriate:</p>

<pre class="verbatim"><a name="normalize"></a>  sub <span class="m">normalize</span> <span class="s">{</span> <a class="l_k" href="functions/join.html">join</a> <span class="q">&#39; &#39;</span><span class="cm">,</span> <span class="i">$_</span>[<span class="n">0</span>]<span class="cm">,</span> <span class="i">@</span>{<span class="i">$_</span>[<span class="n">1</span>]} <span class="s">}</span></pre>

          } 

          return $line;

        }</pre><p>At 10:23, this function generates the 10th line of a data file; at

will only see the $problem_type argument.  To fix this, include the

current hour in the normalizer:</p>

<pre class="verbatim"><a name="normalize"></a>        sub <span class="m">normalize</span> <span class="s">{</span> <a class="l_k" href="functions/join.html">join</a> <span class="q">&#39; &#39;</span><span class="cm">,</span> <span class="s">(</span><a class="l_k" href="functions/localtime.html">localtime</a><span class="s">)</span>[<span class="n">2</span>]<span class="cm">,</span> <span class="i">@_</span> <span class="s">}</span></pre>

would in scalar context, you can have the normalizer function select

its behavior based on the results of <code class="inline"><a class="l_k" href="functions/wantarray.html">wantarray</a></code>.  Even if called in

a list context, a normalizer should still return a single string.</p>

</h2>

ordinary Perl hash variable.  However, you might like to have the

values cached on the disk, so that they persist from one run of your

program to the next, or you might like to associate some other

interesting semantics with the cached values.</p>

actually <i>two</i> caches, one for scalar values and one for list values.

When your function is called in scalar context, its return value is

cached in one hash, and when your function is called in list context,

its value is cached in the other hash.  You can control the caching

behavior of both contexts independently with these options.</p>

 must either be one of

the following four strings:</p>

<p>or else it must be a reference to a list whose first element is one of

.</p>

<ul>

</b>

 means that return values from the function will be cached in

an ordinary Perl hash variable.  The hash variable will not persist

after the program exits.  This is the default.</p>

</li>

</b>

 allows you to specify that a particular hash that you supply

will be used as the cache.  You can tie this hash beforehand to give

it any behavior you want.</p>

<p>A tied hash can have any semantics at all.  It is typically tied to an

on-disk database, so that cached values are stored in the database and

retrieved from it again when needed, and the disk file typically

 for more

complete details about <code class="inline"><a class="l_k" href="functions/tie.html">tie</a></code>.</p>

<p>A typical example is:</p>

whose name is in <code class="inline"><span class="i">$filename</span></code>

.  The cache will persist after the

program has exited.  Next time the program runs, it will find the

come to run your real program the memoized function will be fast

because all its results have been precomputed.</p>

</li>

</b>

<p>This option is no longer supported.  It is still documented only to

aid in the debugging of old programs that use it.  Old programs should

 option instead.</p>

<p>is merely a shortcut for</p>

        <span class="s">{</span> <a class="l_k" href="functions/my.html">my</a> <span class="i">%cache</span><span class="sc">;</span>

        <span class="s">}</span>

</li>

</b>

 means that you never expect to call the function in scalar

should abort the program.  The error message is one of</p>

<pre class="verbatim">  `foo' function called in forbidden list context at line ...

        `foo' function called in forbidden scalar context at line ...</pre></li>

</b>

 normally means the function does not distinguish between list

and sclar context, and that return values in both contexts should be

 means that list context

return values should be stored in the same hash that is used for

 means the

 for both,

but it probably does something useful.</p>

<p>Consider this function:</p>

<pre class="verbatim"><a name="pi"></a> sub <span class="m">pi</span> <span class="s">{</span> <span class="n">3</span><span class="sc">;</span> <span class="s">}</span></pre>

:</p>

<pre class="verbatim">    <span class="i">$x</span> = <span class="i">pi</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span>

    <span class="s">(</span><span class="i">$y</span><span class="s">)</span> = <span class="i">pi</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span>

 in the scalar cache; the second

caches the list <code class="inline"><span class="s">(</span><span class="n">3</span><span class="s">)</span></code>

 in the list cache.  The third call doesn't call

 function; it gets the value from the scalar cache.</p>

 is a waste of time, and storing

 use the same cache for scalar and list

context return values, so that the second call uses the scalar cache

 ends up being called only

once, and both subsequent calls return <code class="inline"><span class="n">3</span></code>

 from the cache, regardless

of the calling context.</p>

 is when you want both kinds of return values

stored in the same disk file; this saves you from having to deal with

two disk files instead of one.  You can use a normalizer function to

keep the two sets of return values separate.  For example:</p>

<pre class="verbatim">        <a class="l_k" href="functions/tie.html">tie</a> <a class="l_k" href="functions/my.html">my</a> <span class="i">%cache</span> <span class="cm">=&gt;</span> <span class="q">&#39;MLDBM&#39;</span><span class="cm">,</span> <span class="q">&#39;DB_File&#39;</span><span class="cm">,</span> <span class="i">$filename</span><span class="cm">,</span> ...<span class="sc">;</span></pre>

        <span class="sc">;</span></pre>

<pre class="verbatim"><a name="n"></a>  sub <span class="m">n</span> <span class="s">{</span>

          <a class="l_k" href="functions/my.html">my</a> <span class="i">$context</span> = <a class="l_k" href="functions/wantarray.html">wantarray</a><span class="s">(</span><span class="s">)</span> ? <span class="q">&#39;L&#39;</span> <span class="co">:</span> <span class="q">&#39;S&#39;</span><span class="sc">;</span>

</li>

</ul>

<a name="OTHER-FACILITIES"></a><h1>OTHER FACILITIES</h1>

</h2>

 function that you can import if you want to.

Why would you want to?  Here's an example: Suppose you have your cache

tied to a DBM file, and you want to make sure that the cache is

exits normally, this will happen anyway, but if someone types

control-C or something then the program will terminate immediately

without synchronizing the database.  So what you can do instead is</p>

 accepts a reference to, or the name of a previously

memoized function, and undoes whatever it did to provide the memoized

version in the first place, including making the name refer to the

unmemoized version of the function.</p>

<p>If you ask it to unmemoize a function that was never memoized, it

croaks.</p>

</h2>

 will flush out the caches, discarding <i>all</i>

the cached data.  The argument may be a function name or a reference

to a function.  For finer control over when data is discarded or

this package.</p>

 will attempt to

 

method, this will cause a run-time error.</p>

 option

as its cache.  Then you can examine or modify the hash at any time in

any way you desire.  You may flush the cache by using <code class="inline"><span class="i">%hash</span> = <span class="s">(</span><span class="s">)</span></code>

<a name="CAVEATS"></a><h1>CAVEATS</h1>

<p>Memoization is not a cure-all:</p>

<ul>

<pre class="verbatim"><a name="f"></a>  sub <span class="m">f</span> <span class="s">{</span>

          <a class="l_k" href="functions/time.html">time</a><span class="sc">;</span>

        <span class="s">}</span></pre>

course, and the memoized version of this function will call <code class="inline"><a class="l_k" href="functions/time.html">time</a></code> once

to get the current time, and it will return that same time

every time you call it after that.</p>

        <span class="s">}</span></pre>

<p>This function accepts two arguments, adds them, and prints their sum.

Its return value is the numuber of characters it printed, but you

that.  If you memoize this function, you will get the result you

expect the first time you ask it to print the sum of 2 and 3, but

subsequent calls will return 1 (the return value of

<li>

<p>Do not memoize a function that returns a data structure that is

modified by its caller.</p>

 returns a list of users somehow,

 throws away the first user on the list and prints the

rest:</p>

<pre class="verbatim"><a name="main"></a>       sub <span class="m">main</span> <span class="s">{</span>

          <span class="c"># Do something to get a list of users;</span>

          \<span class="i">@users</span><span class="sc">;</span>  <span class="c"># Return reference to list.</span>

        <span class="s">}</span></pre>

 here, it will work right exactly once.  The

 

will discard the first element from the referenced list.  The next

; it will

just return the same reference to the same list it got last time.  But

 will

erroneously remove another element from it.  The list will get shorter

.</p>

<p>Similarly, this:</p>

<pre class="verbatim">  <span class="i">$u1</span> = <span class="i">getusers</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span>    

        <span class="i">$u2</span> = <span class="i">getusers</span><span class="s">(</span><span class="s">)</span><span class="sc">;</span>    

        <a class="l_k" href="functions/pop.html">pop</a> <span class="i">@$u1</span><span class="sc">;</span></pre>

<p>will modify $u2 as well as $u1, because both variables are references

 not been memoized, $u1 and $u2

would have referred to different arrays.</p>

</li>

<pre class="verbatim"><a name="square"></a>    sub <span class="m">square</span> <span class="s">{</span>

      <span class="i">$_</span>[<span class="n">0</span>] * <span class="i">$_</span>[<span class="n">0</span>]<span class="sc">;</span>

    <span class="s">}</span></pre>

number in the hash is necessarily going to take a lot longer than a

single multiplication.  There really is no way to speed up the

 function.</p>

<p>Memoization is not magical.</p>

</li>

</ul>

<a name="PERSISTENT-CACHE-SUPPORT"></a><h1>PERSISTENT CACHE SUPPORT</h1>

<p>You can tie the cache tables to any sort of tied hash that you want

, and

.  For example,</p>

<p>works just fine.  For some storage methods, you need a little glue.</p>

 method, so included in this

)</p>

hash to disk and retrieve it again, but you can't modify the hash while

it's on the disk.  So if you want to store your cache table in a

memoize the function, and stored back at the time you unmemoize the

function (or when your program exits):</p>

<pre class="verbatim">        <a class="l_k" href="functions/tie.html">tie</a> <a class="l_k" href="functions/my.html">my</a> <span class="i">%cache</span> <span class="cm">=&gt;</span> <span class="q">&#39;Memoize::Storable&#39;</span><span class="cm">,</span> <span class="i">$filename</span><span class="sc">;</span>

<pre class="verbatim">        <a class="l_k" href="functions/tie.html">tie</a> <a class="l_k" href="functions/my.html">my</a> <span class="i">%cache</span> <span class="cm">=&gt;</span> <span class="q">&#39;Memoize::Storable&#39;</span><span class="cm">,</span> <span class="i">$filename</span><span class="cm">,</span> <span class="q">&#39;nstore&#39;</span><span class="sc">;</span>

in `network order'.  (See <a href="Storable.html">Storable</a> for more details about this.)</p>

<p>The <code class="inline"><span class="i">flush_cache</span><span class="s">(</span><span class="s">)</span></code>

 function will raise a run-time error unless the

 method.</p>

<a name="EXPIRATION-SUPPORT"></a><h1>EXPIRATION SUPPORT</h1>

<p>See Memoize::Expire, which is a plug-in module that adds expiration

in Perl, and until it is resolved, memoized functions will see a

slightly different <code class="inline"><a class="l_k" href="functions/caller.html">caller()</a></code> and will perform a little more slowly

on threaded perls than unthreaded perls.</p>

 which you

<code class="inline"><span class="i">f</span><span class="s">(</span><span class="s">)</span></code>

 called with no arguments) will not be memoized.  If this

is a big problem, you can supply a normalizer function that prepends

<code class="inline"><span class="q">&quot;x&quot;</span></code>

 to every key.</p>

<a name="MAILING-LIST"></a><h1>MAILING LIST</h1>

<p>To join a very low-traffic mailing list for announcements about

.</p>

<a name="AUTHOR"></a><h1>AUTHOR</h1>

), Plover Systems co.</p>

 Page at <a href="http://www.plover.com/~mjd/perl/Memoize/">http://www.plover.com/~mjd/perl/Memoize/</a>

for news and upgrades.  Near this page, at

<a href="http://www.plover.com/~mjd/perl/MiniMemoize/">http://www.plover.com/~mjd/perl/MiniMemoize/</a> there is an article about

in 2002, possibly under the title <i>Perl Advanced Techniques

Handbook</i>.  It will also be available on-line for free.  For more

information, visit <a href="http://perl.plover.com/book/">http://perl.plover.com/book/</a> .</p>

.  This mailing

list is for announcements only and has extremely low traffic---about

two messages per year.</p>

helpful suggestions, to Jonathan Roy (again) for finding a use for

<code class="inline"><span class="i">unmemoize</span><span class="s">(</span><span class="s">)</span></code>

, to Philippe Verdret for enlightening discussion of

, to Nat Torkington for advice I ignored, to Chris

Nandor for portability advice, to Randal Schwartz for suggesting the

 function, and to Jenda Krynicky for being a light in

the world.</p>

<p>Special thanks to Jarkko Hietaniemi, the 5.8.0 pumpking, for including

          <!--<select name="r"><option value="1" selected>Go to top result<option value="0">Show results list</select>-->

        </form>

      </p>

      <h2>Labels:</h2>

      <p>

        <a href="#" onClick="addLabel('Memoize','Memoize.html')">Add this page</a>