Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

comment on

( [id://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":



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others taking refuge in the Monastery: (3)
As of 2024-03-19 05:06 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found