The Series Operator and Memoization

Masak recently posted on the series operator solution to Pascal’s Triangle. I’d like to focus on an important property of his final solution that hasn’t been much discussed yet.

But first, let me back up and consider another well-known problem with similar properties: the Fibonacci series. A straightforward recursive solution looks like this in Perl 6:

sub Fibonacci($n) {
    return $n if $n == 0 | 1;
    Fibonacci($n - 1) + Fibonacci($n - 2);
}

This nicely implements the definition, but it has one critical problem — it is incredibly inefficient. (And not just in Rakudo — in any language!) The reason is that calculating Fibonacci(N) requires all the work of calculating Fibonacci(N-1) and Fibonacci(N-2). The number of subroutine calls involved grows as fast as the series does.

The standard recursive technique for dealing with this problem is called memoization. Basically, you cache the values which have already been computed somewhere, so you only need to compute them once. That’s a bit awkward to implement by hand — it roughly doubles the complexity of the routine, I’d say. Luckily, lots of languages have automatic ways to apply memoization. Perl 6 is supposed to, with the “is cached” modifier to a subroutine definition, but Rakudo doesn’t have it implemented yet.

That’s okay, because there is more than one way to do it, and there is a great way which is available already in Rakudo.

> my @Fibonacci := (0, 1, -> $a, $b { $a + $b } ... *); 1;
1
> say @Fibonacci[5]
5
> say @Fibonacci[10]
55
> say @Fibonacci[30]
832040

(I’ve used parentheses instead of do because that’s how I roll, but otherwise this is exactly the same idea as Masak’s solution. The additional 1; is needed only because I typed this into the REPL, and without it the REPL will try to evaluate the entire infinite series so it can print it out.)

You can’t see it here, of course, but calculating these numbers was very quick. That’s because this solution using the series operator is equivalent to writing a very smart memoization. Infinite lists in Perl 6 are implemented (roughly speaking) with an array of values that have been already calculated, and an iterator which knows how to calculate further values as needed.

So when you say @Fibonacci[5] the first time, the list calls the iterator generated by the series operator to get the first six values, storing them in @Fibonacci[0] through @Fibonacci[5]. (Those values are generated in a straightforward iterative way, so it is very efficient.) When you then say @Fibonacci[10] those first six values are still there, and only the next five values must be calculated. If at that point you said @Fibonacci[8], that is just a simple array lookup of the already calculated value!

Think about it. It would take a very smart automatic memoizer to somehow figure out that the function would only be called when $n was a non-negative integer, so that an array could be used to efficiently cache the results. Using a series operator this way gets you that kind of performance automatically already in Rakudo.

So it’s a double win. Using the series operator is not only the most succinct way to express this series in Perl 6. It’s also an extremely efficient way of calculating the series.

About these ads

One Response to “The Series Operator and Memoization”

  1. Series, Memoization, and Limits « Just Rakudo It Says:

    [...] Just Rakudo It I Never Metaop I Didn't Like « The Series Operator and Memoization [...]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

%d bloggers like this: