Memoization

Imagine you are working on a complex report and realize you have already calculated the same set of numbers three times in different sections. You could spend another hour re-doing the work, or you could look up your previous notes and finish in minutes. Memoization is that act of looking up your notes so you never repeat an expensive calculation. It turns tasks that would take centuries to complete into ones that finish in milliseconds by remembering past results.

Memoization is the idea of remembering the answers to questions you've already answered, so you don't have to compute them again. Imagine you're a student solving a worksheet of arithmetic problems. Some problems are repeated. If you solve the same problem twice, you waste time. Instead, you keep a small notebook: every time you solve a problem, you write down the problem and its answer. The next time you see it, you just look it up, without doing the arithmetic again. Memoization is exactly that, but for functions in a program. When a function is called with the same arguments a second time, instead of recomputing the result from scratch, the program looks it up in a cache—a temporary storage area. This only works if the function is 'pure'—that is, the same input always gives the same output, and calling it doesn't change anything else in the world. If a function isn't pure, the cache would return stale or wrong answers. Memoization is a way to trade a little extra memory for a lot less time—a classic space-time tradeoff.

Think of a chef preparing a large meal. The recipe has many steps, and some steps are reused. For example, the chef needs to make a stock that is used in three different dishes. Instead of making the stock three times, the chef makes it once, stores it in a container, and then uses it from the container each time. The stock is the result of a function (make_stock) with no arguments. But imagine the stock recipe depends on the type of stock (chicken, vegetable, beef). If the chef is making both a chicken soup and a chicken sauce, both need chicken stock. The chef can make chicken stock once, label the container 'chicken stock', and reuse it. The label is the cache key; the container is the cache. The chef would not make it again unless it was needed for a different kind. This analogy holds until we consider that the stock might spoil—in a program, the cache doesn't spoil. But it can grow too large, so we might need to evict old entries, just like a chef might discard old stock to make room in the fridge. That's the eviction policy part of memoization.

Memoization is a technique where a function's results are stored in a cache keyed by its arguments, so that repeated calls with the same arguments return the stored result immediately instead of recomputing it.

Memoization is a specific way to implement dynamic programming, which is a method for solving complex problems by breaking them into smaller, overlapping sub-problems. It is also a direct application of the space-time tradeoff you will study: you spend memory on a cache to save computation time.