Beefy Boxes and Bandwidth Generously Provided by pair Networks Joe
No such thing as a small change
 
PerlMonks  

Memoize

by ariels (Curate)
on Nov 30, 2000 at 16:06 UTC ( #44112=modulereview: print w/ replies, xml ) Need Help??

Item Description: Make your functions faster by trading space for time

Review Synopsis:

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

Comment on Memoize
Select or Download Code

Back to Reviews

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: modulereview [id://44112]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (5)
As of 2014-04-20 01:54 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    April first is:







    Results (485 votes), past polls