Ovid

Memoize is a great module. It's one of those fantastic modules that, when you need it, does exactly what you need. Like when you're perfectly healthy and want to beg for money so reach for a crutch. That's how many people use Memoize.

Don't get me wrong: I've been lazy and abused this module myself. It's quick, it's easy, and as it says on the tin: "Make functions faster by trading space for time". So you know there's a trade-off: you save time, but your memory overhead increases. That's OK. Memory is cheap. No argument I might put down will dissuade you on that point.

But is it really faster?

Let's look at how Fibonacci is defined in the documentation:

sub fib {
    my $n = shift;
    return $n if $n < 2;
    fib($n-1) + fib($n-2);
}

Now it's pointed out, quite rightly, that this function is very slow. Sit down and work it out on paper and you'll find out that it grows exponentially. (Dominus is a smart guy and I'm pretty damned certain he knows better solutions and chose this for an example.) So if you wanted to compute the 200th fibonacci number, you can't use this function ... unless you cheat and do this:

use Memoize 'memoize';
memoize('fib');
....

On my box, the wait starts to get annoyingly long when N starts to hit the mid-thirties. Without caching, there's no way I could compute the 200th Fibonacci number. Without caring about the actual number, the time is around 0.004 seconds. Not bad, eh? Four one-thousandths of a second. Pretty darn good. Of course, I'm trading memory for this, but so what? I want to be fast, right?

Except that you might be familiar with this algorithm:

sub fib2 {
    my $n = shift;
    my ( $last, $fib ) = ( -1, 1 );
    for ( 0 .. $n ) {                                                       
        my $new = $fib + $last;
        $last = $fib;
        $fib  = $new;
    }
    return $fib;
}

Now, instead of computing it recursively, you're computing it iteratively ... and forward. There's no duplication of results (this also tends to be how you work it out by hand).

The time for the 200th number? Around 0.00008 seconds on my box, or almost 50 times faster (with less memory consumption to boot. In this example it's too trivial to be worth discussing, but this is not always the case!).

But maybe I cheated? After all, Memoize has lots of code to handle special cases. Isn't algorithms really about choosing the right tool for the right job? Let me hand-craft my cache:

{
    my %cache;

    sub fib {
        no warnings 'recursion';
        my $n = shift;
        return $n if $n < 2;
        return $cache{$n} //= fib( $n - 1 ) + fib( $n - 2 );
    }
}

Sadly, that takes about 0.0005 seconds, almost ten times as fast as Memoize, but still far slower than our non-memoized solution.

Understanding algorithms is about choosing the right tool for the job, but if you don't know your tools, you can't choose them. The next time you want to memoize something, ask yourself if you really came up with the most efficient implementation. You might be surprised.

Full code in case you want to play with it yourself:

#!/usr/bin/perl

use v5.14.0;
use strict;
use warnings;
use Time::HiRes qw(gettimeofday tv_interval);

use Memoize 'memoize';

sub timefor(&$) {
    my $start = [gettimeofday];
    $_[0]->();
    say sprintf "$_[1]: took %s time" => tv_interval($start);
}

memoize('fib1');

sub fib1 {
    my $n = shift;
    return $n if $n < 2;
    fib1( $n - 1 ) + fib1( $n - 2 );
}

sub fib2 {
    my $n = shift;
    my ( $last, $fib ) = ( -1, 1 );
    for ( 0 .. $n ) {
        my $new = $fib + $last;
        $last = $fib;
        $fib  = $new;
    }
    return $fib;
}

{
    my %cache;

    sub fib3 {
        no warnings 'recursion';
        my $n = shift;
        return $n if $n < 2;
        return $cache{$n} //= fib3( $n - 1 ) + fib3( $n - 2 );
    }
}

timefor { say fib1(200) } 'backwards';
timefor { say fib2(200) } 'forward';
timefor { say fib3(200) } 'our cache';

Update: The "forward", or fib2 algorithm runs in Ɵ(n) time, but you can actually calculate fibonacci sequences in Ɵ(log n) time with matrix multiplication.