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%       --
[download]

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.

Chapter 3 of Higher Order Perl develops the memoize technique and the module - I recommend reading it if you are interested in how memoization works.

Actually, I would recommend it in general if you want to become a better programmer. It is an amazing book.

It really helps you to break out of procedural thinking and learn new techniques.



-pete
"Worry is like a rocking chair. It gives you something to do, but it doesn't get you anywhere."