Memoization facts for kids

In computing, memoization is a clever trick used to make computer programs run faster. It works by "remembering" the results of calculations that take a lot of time. If the program needs the same answer again, it simply looks up the saved result instead of doing the calculation all over again.

Memoization is a type of caching. Think of it like a computer's special notebook where it writes down answers to problems so it doesn't have to solve them repeatedly.

What's in a Name?

The word memoization was created by a person named Donald Michie in 1968. It comes from the Latin word memorandum, which means 'to be remembered'. You might know the shorter version, 'memo'. So, memoization means 'turning the results of a function into something to be remembered'.

Even though it sounds a lot like 'memorization', memoization has a special meaning in the world of computers.

How Memoization Works

A memoized function is like a smart student who remembers the answers to certain math problems. When you give it the same problem again, it doesn't solve it from scratch. Instead, it just gives you the answer it already remembered. This saves a lot of time!

This trick is great for speeding up programs. However, it uses more computer memory to store all those remembered answers. So, it's a trade-off: you gain speed but use more memory. This balance between time and space is a big idea in computer science.

Let's look at an example: calculating a factorial. A factorial of a number (like 5!) means multiplying that number by every whole number smaller than it, down to 1. So, 5! = 5 × 4 × 3 × 2 × 1 = 120.

Here's a simple way a computer might calculate a factorial without memoization:

function factorial (n is a number) if n is 0 then return 1 else return factorial(n – 1) times n end if end function

If you ask this function to calculate `factorial(5)`, it will call itself many times: `factorial(5)` calls `factorial(4)`, which calls `factorial(3)`, and so on, until it reaches `factorial(0)`. Each of these calls takes a little bit of time.

Now, here's how a memoized version would work:

function factorial (n is a number) if n is 0 then return 1 else if n is in lookup-table then [Is the answer already saved?] return lookup-table-value-for-n [Yes! Give the saved answer.] else let x = factorial(n – 1) times n [Calculate the answer.] store x in lookup-table for n [Save the answer for later.] return x end if end function

With memoization, if you calculate `factorial(5)`, the program will save the results for 5!, 4!, 3!, 2!, 1!, and 0! in its "lookup table." If you later ask for `factorial(3)`, it will already have the answer saved and give it to you instantly! If you ask for `factorial(7)`, it only needs to calculate 7! and 6!, because 5! and all smaller factorials are already saved.

This way, a memoized function gets faster the more you use it, because it keeps building up its memory of answers.

Other Ways Memoization Helps

Automatic Memoization

Sometimes, programmers add memoization to their code themselves. But for certain types of functions, computers can even add memoization automatically! This means the computer can figure out on its own when to save results to make things faster.

Imagine a special helper function that wraps around your original function. When you call the helper, it first checks if the answer is already saved. If not, it calls your original function, saves the answer, and then gives it back to you. This makes your original function "memoized" without you having to change its inner workings.

Helping Parsers

Memoization is also very useful in programs called parsers. Parsers are like language detectives for computers. They break down sentences (or computer code) to understand their structure.

Sometimes, a parser might try to understand a sentence in one way, fail, and then have to go back and try another way. This is called "backtracking." If the parser has to re-read the same part of the sentence many times, it can be very slow.

Memoization helps here! When a parser analyzes a part of a sentence, it can save the result. If it ever needs to analyze that exact same part again (because of backtracking), it can just look up the saved result. This stops the parser from doing the same work over and over, making it much faster.

For example, if a parser is looking for a specific pattern in a long string of 'x's, it might analyze the 'x's once. If it then backtracks and needs to check the 'x's again, it can use the memoized result instead of re-reading all the 'x's. This saves a lot of time, especially for very long strings.

See also

In Spanish: Memoización para niños