Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??

Description

Memoization speeds up calculation of a function by storing its previously-computed values. MJD's excellent Memoize module memoizes (almost) any function you ask it to. If you use Memoize;, applying this optimisation can be as simple as saying memoize 'slow_function';.

Additional methods exist, allowing such things as persistant storage of memoized values.

Why should I use it?

Memoization is not a technique for everyday use. Only pure functions (functions which are executed only for their return values, not for any side effects) can be memoized. It's the sort of module you should download and learn how (and when) to use.

Eventually you'll write a slow routine that gets called in a slow loop. If only a small number of different argument combinations get passed to the routine, it's an excellent candidate for memoization.

The documentation contains several examples, some of which can serve as ideas for usage. The section on persistant storage of the cache is particularly noteworthy.

Why should I read it?

The documentation, code and a Perl Journal article make excellent associated reading, sure to improve your Perl. Both explain in detail what memoization is, and how (and when!) to use it. In particular, the article explains how the module performs its magic, by giving a very short (but complete!) implementation of the principle routine, memoize.

Ways to use the module are mentioned, with examples:

  • Simple memoization
  • Using a batch process to "pre-memoize" some values persistantly
  • Memoizing list and scalar context together (normally the module keeps the contexts separate).
  • Support for Memoize::Expire.
  • Memoization as a lightweight substitute for dynamic programming.
  • Memoization as a clearer replacement for the Orcish maneuver.

You should also read the documentation (or the article), paying attention to the routine's limitation regarding functions taking multiple arguments which may contain the contents of $; (see "Why shouldn't I use it", below).

Finally, the author of this review is mentioned in the module's documentation. This gives at least one person an additional reason to read the documentation.

Why shouldn't I use it?

Most likely, because your problem doesn't need it.

If your problem does need memoization, you might still need to help the module a bit.

  • If your routine takes multiple arguments, Memoize codes them using the single key join $; , @_; if your arguments may contain the contents of $; (in particular, if one of the arguments is binary data), you might need to do some extra work.
  • If your routine takes a complex data structure as argument, you'll probably also need to do some extra work to use the module.
The documentation describes both problems and how to solve them. Neither is a showstopper, but it is probably worth your while to know about these problems before you run into them.

Probably the single biggest drawback of memoization is that it doesn't work for functions with side effects. This is nothing to do with Memoize, and everything to do with the technique. Unfortunately, there is no way the module can check this for you. Blindly applying memoize to every slow function in your program will not work, and will cause your program to fail without warnings! Make sure to understand what you are doing, before you do it.

2001-03-15 Edit by Corion : Removed spurious links


In reply to Memoize by ariels

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others perusing the Monastery: (5)
    As of 2014-09-18 05:14 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      How do you remember the number of days in each month?











      Results (108 votes), past polls