Writing Each Answer Down Once

Last timeSolving the Same Thing Over and Over

Keep every answer the moment it is computed and return it when asked again, and the tree of calls collapses to one call per distinct question.

The whole repair

The previous lesson ended with a sentence: anything done repeatedly can be

done once and remembered. Here is that sentence as code.

Keep a store, empty at the start. At the very top of the method, before

anything else, look in the store for this question. If it is there, return the

stored answer immediately. Otherwise compute the answer as before, put it in

the store, and return it.

FIG 1Four days becomes instant

python

def ways(n, seen={}):
    if n <= 1:
        return 1
    if n in seen:
        return seen[n]  # the check comes first, before any work
    seen[n] = ways(n - 1, seen) + ways(n - 2, seen)
    return seen[n]
import sys
sys.setrecursionlimit(100000)  # the depth is now the only limit left
print(ways(50))  # 20365011074, instant
print(len(str(ways(10000))))  # 2090 digits, also instant

The three lines of logic are untouched. Two lines were added and the method went from four days at fifty to immediate at ten thousand. It is worth sitting with how little changed, because the instinct on meeting a method this slow is to rewrite it rather than to add two lines to it.

Why it collapses

The reason this works is worth stating precisely, because the size of the

improvement looks implausible.

Every call either finds its answer in the store and returns at once, which

costs nothing and makes no further calls, or does not, in which case it

computes and stores. The second case can happen only once per distinct

question, since afterwards the answer is in the store. So the number of calls

that actually do any work is exactly the number of distinct questions.

For the staircase, the distinct questions are the values from zero to $n$ .

That is $n + 1$ of them, each doing one addition. The method that made two

million calls for thirty steps now makes thirty one.

FIG 2The same computation before and after

	calls that do work	calls answered from the	time
thirty steps, before	2692537	0	200
thirty steps, after	31	29	0
fifty steps, before	40730022147	0	345600000
fifty steps, after	51	49	0
ten thousand steps, afte	10001	9999	20

Times are in milliseconds, so the marked cell is four days. The second column is the measure of how much waste there was: before the repair every one of those calls expanded a whole subtree, and after it each returns immediately.

FIG 3What the cost becomes

: how many different argument combinations the method can be called with

This is the formula to reach for whenever a remembered recursion needs costing, and it is usually a few seconds of arithmetic. For the staircase it is n questions times one addition. For a method taking two arguments each ranging to a thousand it is a million questions times whatever one call does.

Counting the questions first

That formula is more useful before writing the method than after, because it

answers the question of whether the repair is going to be enough.

Look at the arguments. If the method takes one number up to $n$ , there are $n$

distinct questions. If it takes two numbers, one up to $n$ and one up to $m$ ,

there are $n$ times $m$ . If it takes a position in a list and a remaining

budget, it is the length multiplied by the number of budget values.

That count is both the running time and, as the next section discusses, the

memory. So a method whose arguments are a position up to a thousand and a

budget up to a thousand will do a million units of work, which is fine. A

method whose arguments are three positions each up to a thousand will do a

thousand million, which is probably not. And a method whose argument is a set

of visited places among thirty has a thousand million distinct questions too,

which is where this approach stops being the answer.

The lesson stops here

3 more paragraphs to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents