note
BrowserUk
<blockquote><i><c>return $fib3_cache{$n} ||= do {</c></i></blockquote>
<p>I'd strongly recommend trading <c>//=</c> for <c>||=</c>. Any function that can return 0, but costs to determine that, looses out as is.
<p>You can get greater benefits still for functions that take low integers as inputs by using an array instead of a hash for the cache:<code>
my @fib4_cache;
sub fib4 {
my $n = shift;
return $fib4_cache[$n] //= do {
$n < 2 ? $n : fib4($n-1) + fib4($n-2)
};
}
__END__
C:\test>memofib.pl
Rate fib1 fib2 fib3 fib4
fib1 88.7/s -- -100% -100% -100%
fib2 219835/s 247838% -- -89% -91%
fib3 2073455/s 2338415% 843% -- -19%
fib4 2551114/s 2877136% 1060% 23% --
</code>
<p>And see the benefits more clearly if you do away with some of the benchmark overheads by loosing the sub wrappers (The module adds its own wrapper internally):<code>
cmpthese(-1, {
fib1 => q{ fib1 20 },
fib2 => q{ fib2 20 },
fib3 => q{ fib3 20 },
fib4 => q{ fib4 20 },
});
__END__
C:\test>memofib.pl
Rate fib1 fib2 fib3 fib4
fib1 87.4/s -- -100% -100% -100%
fib2 223254/s 255377% -- -89% -91%
fib3 2071504/s 2370384% 828% -- -20%
fib4 2579867/s 2952119% 1056% 25% --
</code>
<P>And finally, there's a couple more % to be had:<code>
my @fib5_cache;
sub fib5 {
my $n = shift;
return $fib5_cache[ $n ] //= do {
$n < 2 ? $n
: ( $fib5_cache[ $n-1 ] //= fib5($n-1) )
+ ( $fib5_cache[ $n-2 ] //= fib5($n-2) ) ## corrected; thanks to moriitz
};
}
__END__
C:\test>memofib.pl
Rate fib1 fib2 fib3 fib4 fib5
fib1 89.0/s -- -100% -100% -100% -100%
fib2 218452/s 245352% -- -89% -91% -91%
fib3 2022174/s 2272005% 826% -- -18% -20%
fib4 2478824/s 2785096% 1035% 23% -- -2%
fib5 2537045/s 2850512% 1061% 25% 2% --
</code>
<div class="pmsig"><div class="pmsig-171588">
<hr />
<font size=1 >
<div>With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'</div>
<div>Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.</div>
<div>"Science is about questioning the status quo. Questioning authority". </div>
<div>In the absence of evidence, opinion is indistinguishable from prejudice.
</div>
</font>
</div></div>
1013033
1013033