Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
PerlMonks  

comment on

( #3333=superdoc: print w/replies, xml ) Need Help??
Is Memoize really useful for computations?

For many expensive calculations that are called many times it can be very useful.

The following benchmark compares Ack1() which does no memoisation with Ack2() which is identical, but has been memoised. The results at the bottom show that Ack2() is over 5,448 times faster than Ack1():

#! perl -slw use strict; use Benchmark qw[ cmpthese ]; use Memoize; no warnings 'recursion'; sub Ack1 { my( $M, $N ) = @_; return $N + 1 if $M == 0; return Ack1( $M - 1, 1 ) if $N == 0; return Ack1( $M - 1, Ack1( $M, $N - 1 ) ); } sub Ack2 { my( $M, $N ) = @_; return $N + 1 if $M == 0; return Ack2( $M - 1, 1 ) if $N == 0; return Ack2( $M - 1, Ack2( $M, $N - 1 ) ); } memoize( 'Ack2' ); my %memo; sub Ack3 { my( $M, $N ) = @_; return $memo{ "$M:$N" } //= $N + 1 if $M == 0; return $memo{ "$M:$N" } //= Ack3( $M - 1, 1 ) if $N == 0; return $memo{ "$M:$N" } //= Ack3( $M - 1, Ack3( $M, $N - 1 ) ); } our( $M, $N ) = @ARGV; cmpthese -1, { nomemo => q[ Ack1( $M, $N ) ], Memoise => q[ Ack2( $M, $N ) ], Homebrew => q[ Ack3( $M, $N ) ], }; __END__ C:\test>ack 3 5 Rate nomemo Memoise Homebrew nomemo 34.8/s -- -100% -100% Memoise 189639/s 544863% -- -79% Homebrew 889629/s 2556412% 369% --

However, all is not lost if you cannot use Memoize, as it is not very difficult to do the memoisation yourself. Ack3() does this using a simple hash and it runs nearly 4 times faster than Ack2() and 25,000 time faster than the non-memoised version.


Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.

In reply to Re^5: Anonymous function called in forbidden scalar context by BrowserUk
in thread Anonymous function called in forbidden scalar context by vit

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 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? | Other CB clients
Other Users?
Others chilling in the Monastery: (1)
As of 2022-10-01 07:21 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    I prefer my indexes to start at:




    Results (126 votes). Check out past polls.

    Notices?