[ Perl tips index ]
[ Subscribe to Perl tips ]
Imagine that you have a subroutine that is a function in the mathematical sense. A given set of inputs will always result in the same output. A good example may be a function that determines if a number is prime, or one that picks the largest number from a list. These functions depend only upon their inputs, and produce only their return values.
If our functions take a long time to calculate their results, then we can use a hash to remember the results, so we don't have to calculate them next time:
# Calculate the Fibonacci number for a given input my %fib_results; # our cache sub fibonacci { my $n = shift;
# See if we've already cached our result if(exists $fib_results{$n}) { return $fib_results{$n}; }
# Base cases if($n == 0 || $n == 1) { $fib_results{$n} = $n; return $n; }
# Calculate the result my $result = fibonacci($n - 1) + fibonacci($n - 2);
# Store result and return answer $fib_results{$n} = $result; return $result; }
This version is many times faster than one which doesn't remember the results, however this is achieved at a loss to readability. Instead of being able to look at the function and immediately understand how it works, we have to wade through all of the caching work. Further, there is a risk that our caching itself may be introducing bugs. For example if we accidently wrote:
# Base cases if($n == 0 || $n == 1) { $fib_results{$n} = 1; # Oops! return $n; }
then we'll get some very odd results (fibonacci(0)
should return 0)..
Fortunately there is a Perl module Memoize that comes standard with Perl which does this caching work for us. Using it allows us to write:
use Memoize; memoize('fibonacci');
# Then later...
# Calculate the Fibonacci number for a given input
sub fibonacci { my $n = shift;
# Base cases if($n == 0 || $n == 1) { return $n; }
# Calculate our result return fibonacci($n - 1) + fibonacci($n - 2); }
Now the clutter from caching is gone and it's easy to see that the code is
correct. Further, if we ever want to remove the caching for any reason we
can just comment out the call to memoize()
Memoize
accepts the following options where required:
INSTALL
option to specify a new name for
the cached code:
memoize('fibonacci', INSTALL => 'new_fibonacci');
memoize
with a normalize
subroutine which tells Memoize which argument lists should be treated as
identical.
This is also important if you are passing references to a memoized function.
memoize('some_subroutine', NORMALIZER => 'some_sub_normalizer');
memoize
a subroutine which uses program, environment, external or temporal
state data, then the results for the first call to that subroutine will be
correct but all later calls may receive out of date information.
Benchmark
.
[ Perl tips index ]
[ Subscribe to Perl tips ]
This Perl tip and associated text is copyright Perl Training Australia. You may freely distribute this text so long as it is distributed in full with this Copyright noticed attached.
If you have any questions please don't hesitate to contact us:
Email: | contact@perltraining.com.au |
Phone: | 03 9354 6001 (Australia) |
International: | +61 3 9354 6001 |
Copyright Perl Training Australia. Contact us at contact@perltraining.com.au