Not Memoization

Sometimes you need a better algorithm, rather than papering over the cracks with optimisation

Sometimes memoization is a useful technique for optimisation, but when you see it explained,it is often demonstrated using little explanatory code or algorithms that show the technique itself well, but are not the best way of achieving their supposed purpose. So you may see a small Fibonacci function for example, that demonstrates memoization well, but is a bad way of calculating Fibonacci numbers.

The same is true of recursion. You will often see something like this factorial function used to demonstrate recursion:

def fact(n: Int) : BigInt = {
    assert(n>=0, "factorial is only defined over non-negative integers")
    if(n==0) then 1
    else fact(n-1) * n
}

...and the article will then go on to demonstrate how to get the tail call optimisation to work so you don't run out of stack space. Or alternatively, will use this as an example of how you memoize a recursive function. The fact is that this is just a really bad way to write a factorial function. Here's one that is not bad:

def fact(n: Int) = {
    assert(n>=0, "factorial is only defined over non-negative integers")
    (BigInt(1) /: (1 to n)) (_*_)
}

Note that we don't need to rely on any special optimisations and this solution runs in constant space and in O(n) time. All we are doing is folding over the range from 1 to the n and multiplying as we go. To put it another way, we are going from the bottom up. Amusingly when we go from the bottom up, we get a function application that looks like butt-cheeks (I can't be the only person to have noticed that).

Now it doesn't take a genius to figure out how we use a memoization-like technique to optimise this if we want to. (I know that it can't because I thought of how to optimise it and I'm no genius)

object Factorial {
    import scala.collection.mutable.ArrayBuffer

    private val cache : ArrayBuffer[BigInt] = new ArrayBuffer()
    cache += 1
    cache += 1

    def apply(n: Int) = {
        assert(n>=0, "Factorial is only defined over non-negative integers")
        if(n>cache.length-1) {
            for(idx<-cache.length to n)
                cache += cache(idx-1) * idx
        }

        cache(n)
    }
}

So we make an array and store the intermediate results in it so that if we are called later for a value that we have already computed, we can simply return it from the array. Because we are using an array, the lookup happens in constant time with little or no constant overhead, rather than using a map or hash as is usually required for general memoization. We can do this because we know the space of inputs is not sparse - we need to compute every intermediate value anyway so we may as well cache them.

This is not memoization because what we are caching is not (just) the result of the function invocation but all partial results. As such, our optimisation has more in common with techniques used in dynamic programming.

The point is that writing the best algorithm is almost always the best optimisation you can do, and if you're jumping through hoops to optimise something, it may be because there's a better way to do it. In the words of Nadia Boulanger, "Never strain to avoid the obvious".

P.S. If you're computing Fibonacci numbers recursively, you are living in a state of sin. Please use the closed form solution. Thanks.


Unless otherwise specified the contents of this page are copyright © 2015 Sean Hunter. This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.