Understanding Memoization

What is memoization?

From our good friend wikipedia:

In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

Practical Example

Imagine if your web application had a has_permission method on your user model that was very expensive to calculate. Because of memoization, if that method is called multiple times, we can cache the result. This would mean that the expensive calculation would only be done once. Every subsequent call to the method would just return the cached value. In rails this would look like:

class User < ActiveRecord::Base
  def has_permission
    @has_permission ||= expensive_calculation
  end
end

Fibonacci Example

Another way to understand this concept is through the classic fibonacci problem.

This problem can be solved recursively:

def fib(num)
  return 0 if num == 0
  return 1 if num == 1
  fib(num - 1) + fib(num - 2)
end

Essentially for every fibonacci number we want to calculate, we find out the values of the previous two fibonacci number’s and sum them up. If we map out what happens with something like fib(4), we will notice that we have have a lot of duplicated calculations.

                            fib(4)
                   fib(3)            fib(2)
             fib(2)    fib(1)   fib(1)   fib(0)
        fib(1)   

So fib(1) is calculated 3 times, and fib(2) is calculated twice. That may not seem like a lot, but imagine if we started with fib(100). (To get an idea, for fib(10), fib(1) is calculated 55 times)

In programming we always want to do as little work as possible. If we calculate a value once, it would be nice if we didn’t have to calculate it again. This is the whole concept of memoization. Before returning fib(num -1) + fib(num -2) we want to check if fib(num) has been calculated. If it has been calculated, great, we just return it. If not, we calculate and then save it for future use. Here is a code example:

def fib(num, memo)
  return 0 if num == 0
  return 1 if num == 1
  return memo[num] if memo[num] # return the value if we have already 
                                # calculated memo[num]
  result = fib(num - 1, memo) + fib(num - 2, memo)
  memo[num] = result # store the result!
  result
end

Because of memoization, every fib(num) is only ever calculated once improving the performance of our code.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s