CUFP
tobyink
<p>For functions which are non-volatile (i.e. the same inputs will always produce the same outputs) with no side-effects, it often makes sense to "memoize" them. That is, cache the results for the next time they're called.</p>
<p>This is an especially good idea in the case of recursive functions. The following benchmark script illustrates the massive speed up.</p>
<c>
use strict;
use warnings;
use Memoize;
use Benchmark 'cmpthese';
sub fib1 {
my $n = shift;
return $n if $n < 2;
return fib1($n-1) + fib1($n-2);
}
sub fib2 {
my $n = shift;
return $n if $n < 2;
return fib2($n-1) + fib2($n-2);
}
memoize('fib2');
my %fib3_cache;
sub fib3 {
my $n = shift;
return $fib3_cache{$n} ||= do {
$n < 2 ? $n : fib3($n-1) + fib3($n-2)
};
}
for (0..5) {
die "something bad" unless fib1($_)==fib2($_);
die "something bad" unless fib1($_)==fib3($_);
}
cmpthese(-1, {
fib1 => sub { fib1 20 },
fib2 => sub { fib2 20 },
fib3 => sub { fib3 20 },
});
__END__
Rate fib1 fib2 fib3
fib1 18.2/s -- -100% -100%
fib2 37594/s 206668% -- -87%
fib3 289129/s 1590107% 669% --
</c>
<p>The [mod://Memoize] module gives you a pretty decent speed up, without needing to change the guts of the function. Just add <c>memoize('fib2')</c> and the Memoize module will wrap the original function with memoization code.</p>
<p>The manually memoized version is clearly faster still, because it avoids the overhead of function wrapping - the memoization code is added to the guts of the function.</p>
<p>Of course, there's no such thing as a free lunch - you're trading CPU for memory.</p>
<!-- Node text goes above. Div tags should contain sig only -->
<div class="pmsig"><div class="pmsig-757127">
<small><small>
<tt>perl -E'sub Monkey::do{say$_,for@_,do{($monkey=[caller(0)]->[3])=~s{::}{ }and$monkey}}"Monkey say"->Monkey::do'
</tt></small></small>
</div></div>