(This is a cross post from B.P.O ).
Chapter 3 of [Higher Order Perl]<(https://hop.perl.plover.com/) describes various approaches to memoization of an expensive function: private cache and the Memoize module. The book was written in 2005 (Perl was at version 5.8 back then) , so it does not include another way for function caching that is now available : caching through state variables (introduced in Perl 5.10). The Fibonacci example considered in HOP also requires the ability to initialize state hash variables (available since Perl 5.28). The code below contrasts the implementation with a state variable v.s. the memoize module:
use Time::HiRes qw(time);
use Memoize;
sub fib_cache_with_state ($number) {
state %fib = ( 0 => 0, 1 => 1 );
unless ( exists $fib{$number} ) {
$fib{$number} = fib_cache_with_state( $number – 1 ) +
fib_cache_with_state( $number – 2 );
}
return $fib{$number};
}
memoize ‘fib‘;
sub fib ($number) {
return $number if $number < 2;
return fib( $number – 1 ) + fib( $number – 2 );
}
my $number = 80;
## using the memoize module
my $start_time = time;
my $fi1 = fib($number);
my $end_time = time;
my $dt1 = $end_time – $start_time;
## using a state variable to memoize
$start_time = time;
my $fib2 = fib_cache_with_state($number);
$end_time = time;
my $dt2 = $end_time – $start_time;
printf “Fibonacci of %d with the memoize module took : %.2gn“, $number, $dt1;
printf “Fibonacci of %d with a state variable took : %.2gn“, $number, $dt2;
printf “Speedup state var /memoize module: %.2gn“, $dt1 / $dt2;
say “Difference in calculations : “, $fi1 – $fib2;
State variable is faster for CPUs , but the Memoize module is faster for humans. Both of them are great tricks to know 🙂
