Memoization

Remove all spaces and punctuation from a text. In how many ways can it be cut into words again? The Russian «Наполеон» (Napoleon) reads in two: «наполеон» and «на поле он» (“he is on the field”). And a paragraph about Natasha from the third volume of War and Peace reads in twenty-seven billion. Write your own text or choose a ready one: the program counts the readings right in the browser, using a dictionary of 14,871 words of the novel, in the original Russian.

Look at the middle counter. A recursion that honestly tries every reading would make 337,816,617,486 calls on this paragraph: about fourteen hours in Go and two or three days in Python. The program answers in a millisecond because it knows a simple trick: it remembers every answer and does not compute it a second time. There are only 133 distinct questions here: “in how many ways can the text be read from letter number i to the end”.

The idea

If a function always returns the same thing for the same arguments, its answers can be remembered: on the first call compute and put into a dictionary, on the next ones take from the dictionary. This is memoization. It changes nothing in the program’s logic, but a recursion that solves the same subproblem many times turns into a recursion that solves each subproblem once.

Here is the recursion from the scene. Let ways(i) be the number of ways to read the text from letter i to the end. Try which word the remainder starts with: if letters i to j − 1 form a word, add ways(j). An empty remainder can be read in one way: ways(n) = 1.

The formula is correct, but the recursion arrives at position j many times, as many as there are ways to read the beginning of the text up to it. And each time it recomputes the whole tail from scratch. Look at the call tree:

The same colour is the same position, that is, the same work done again. In «москвасгорела» (“Moscow burned”) there are 51 calls, while the distinct positions that can be reached at all number 12. Switch the memory on: each position is expanded once, and at later meetings the answer is taken ready, so only the first occurrences remain of the tree. On a short word the saving is modest, but the number of repeats grows exponentially with the length of the text: on the paragraph about Natasha the tree would consist of over three hundred billion nodes.

When it works

Two conditions are needed.

• The function is pure. The result depends only on the arguments: it does not read the time, random numbers, files or global variables that change, and it does not change anything around it. Otherwise an answer from memory may turn out stale, and a repeated call will not perform the side effects it should.
• Subproblems repeat. The same arguments arrive many times. In merge sort each half of the array is sorted once, and memory gives nothing. In the readings problem one position arrives billions of times.

If both conditions hold, the running time is the number of distinct arguments times the work of one call not counting nested ones. Here there are n + 1 positions, and each needs at most 24 pieces checked, the length of the longest word in the dictionary. A paragraph of 232 letters is a few thousand checks instead of hundreds of billions of calls.

Code

In Python memoization is one decorator: @functools.cache (and with a size limit, @functools.lru_cache(maxsize=…)). Go has nothing ready-made, and the memory is a map set up next to the function. The program counts the readings of the paragraph, the calls a recursion without memory would make, and the readings with the fewest and the most words. The shortest reading almost coincides with Tolstoy’s text: 55 words instead of 56, because «так же» (“in the same way”) has stuck together into «также» (“also”), which is a word in the dictionary too.

A measurement on beginnings of the paragraph of growing length. The time axis is logarithmic, so an exponential looks like a straight line: without memory every ten letters multiply the time several times over, with memory the time grows barely noticeably.

The key and the catches

The key is every argument the answer depends on. Here it is one position, because the text and the dictionary do not change while it runs. If the function depends on something else as well, the money left, the step number, the set of items already taken, that must go into the key. A key with something missing gives wrong answers silently.

The key must be immutable. functools.cache stores the arguments in a dictionary, and a list among the arguments gives TypeError: unhashable type. Lists are turned into tuples, sets into frozenset, sets of flags into bit masks. In Go a map key can be a number, a string, a fixed-length array or a struct of such fields, but not a slice.

Memory is not free. Every remembered answer takes space, and an unbounded cache lives as long as the process does. If there are many distinct arguments and mostly the recent ones are needed, use lru_cache(maxsize=…): it throws out whatever has gone longest without being accessed (how such a cache works is in the article on the LRU cache). And a cache on a class method keeps the object self in memory too, a common cause of leaks.

Recursion stays recursion. On a text of five thousand letters a memoizing function goes five thousand calls deep, and Python stops at a thousand by default. Then either the limit is raised with sys.setrecursionlimit, or the same table of answers is filled without recursion, in an order such that the values needed are always already computed, here from the end of the text to the beginning. That is dynamic programming “bottom-up”. Memoization is the same thing “top-down”: the recursion itself finds the order of computation.

What it costs

The time is the number of distinct arguments times the work of one call without nested ones, plus a lookup in the memory dictionary, O(1) on average. The memory is one answer per distinct argument. Without memory the time equals the number of nodes of the call tree, and it can be exponential: naive Fibonacci makes 1.618ⁿ calls, the readings of the paragraph 3.4·10¹¹.

Memoization does not reduce the number of distinct subproblems; it only removes repeats. If the distinct subproblems are themselves exponentially many, as in a full search over all subsets, memory will not help: it will only take up space.

History

The word was coined by the artificial intelligence researcher Donald Michie. In 1968 the journal Nature published his paper “‘Memo’ functions and machine learning”: a function that keeps a note for itself, a memo, and checks it before computing, “learns” from its own experience. During the war Michie worked on breaking ciphers, and later founded one of the first artificial intelligence laboratories.

Problems

The first is the same readings, but for texts of up to five thousand letters, where recursion already hits the depth limit. In the second the numbers on the path of the Collatz conjecture go far beyond the table, and you have to decide what exactly to remember.