Efficiency 0/1

Lesson 20 of 21

Efficiency

Count how a program's work grows with its input, and save work by remembering answers.

Part 1 of 9 Memoization

Remembering answers fib has already worked out

Computed by plain recursion, fib(30) makes 2,692,537 calls, and fib(40) takes about 6 seconds to add up numbers that a loop adds in 40 steps. This lesson starts by finding where those calls go and removing the wasted ones. Then it turns to a question several lessons have touched already: how to tell, before you run a program, whether it will be fast enough.

Most of fib's calls redo work that has already been done. fib(5)\text{fib}(5) calls fib(4)\text{fib}(4) and fib(3)\text{fib}(3), but fib(4)\text{fib}(4) calls fib(3)\text{fib}(3) as well, so fib(3)\text{fib}(3) is worked out twice and fib(2)\text{fib}(2) three times. fib(30)\text{fib}(30) can only ask 31 different questions, fib(0)\text{fib}(0) up to fib(30)\text{fib}(30), so the other 2.69 million calls each ask one of them again. If each answer is written down the first time it is worked out, a repeated call can look it up instead.

Step through the call tree for fib(5)\text{fib}(5) with the memo off, and count how often fib(2)\text{fib}(2) is worked out. Then switch the memo on and step through again.

n5
Calls made: 0 of 15
  • on the stack
  • returned
  • answered from the memo

0 / 30

Call stack

  1. empty

With the memo off, fib(5)\text{fib}(5) makes 15 calls and works out fib(2)\text{fib}(2) three times. With the memo on, it makes 9: fib(2)\text{fib}(2) to fib(5)\text{fib}(5) are each worked out once, and every repeat is answered from the memo without further calls.

Definition

Memoization

Memoization saves each call's result in a table, the memo, keyed by the argument. A call checks the memo first and returns a saved answer at once.

Fibonacci with a memo

Here is fib with a memo, a dictionary that maps each nn to fib(n)\text{fib}(n). The memo is created once, outside the function, so every call reads and writes the same one. A second global name, calls, counts the calls.

Sign up to run
memo = {}
calls = 0

def fib(n):
    global calls
    calls += 1
    if n in memo:
        return memo[n]
    if n < 2:
        result = n
    else:
        result = fib(n - 1) + fib(n - 2)
    memo[n] = result
    return result

print(fib(30))
print(calls)
Python details

global calls lets fib change the global name calls, the way nonlocal lets a function change a name in an enclosing frame. Without it, calls += 1 looks for calls in the call's own frame and stops with an UnboundLocalError.

The answer is still 832,040, and the calls drop from 2,692,537 to 59. Delete the memo check at the top of fib and the same program prints 2,692,537 again. Here is where the 59 comes from. The first call is fib(30)\text{fib}(30), each of fib(2)\text{fib}(2) to fib(30)\text{fib}(30) is worked out once and makes two calls, and every other call is a lookup or a base case that makes none:

1+2⋅29=59 calls, against 2,692,537 without the memo1 + 2 \cdot 29 = 59 \text{ calls, against } 2{,}692{,}537 \text{ without the memo}

In general, memoized fib(n)\text{fib}(n) makes 2n−12n - 1 calls. fib(90)\text{fib}(90), about 2.9×10182.9 \times 10^{18}, takes 179.

The memo costs memory in return: one saved answer for each different argument, 31 of them for fib(30)\text{fib}(30).