Left Arrow.Back

Memoization

Table Of Contents

Multiple circles (hollow on the left, filled on the right). A line connecting them with a square in the middle.

Notes on the computer science optimization technique memoization.

Last Tended-
PlantedSep 2021
StatusSeed
TagsFundamentals
The letter 'A' in upper and lower case.

Definition

In computer science, memoization is an optimization technique. You can take any regular function and memoise it. When memoised, the 1st time the function is called, it performs its calculation and obtains the return value. But before returning that value, it writes down what arguments it was passed, the value it is returning & stores them in a cache.

The next time the function is called, it checks the cache to see if it has seen the new arguments before. If so, it won't perform its calculation, it will just return the value it has written down in the cache. If not, it will perform its calculation & add a new record to the cache. This way, the function never performs its calculation on the same inputs twice. Reducing CPU time (at a cost of more memory). This technique would be used it there was a computationally expensive function that was taking a long time to complete & impacting UX (User Experience).

Without Memoization

Below is an example of a function that takes a number, multiples it by 2, then returns the result. It also logs everytime it performs the calculation. We are calling this function 3 times. The 3rd call has the same argument as the 1st. You can see in the console that the funciton is calculating each time it is called.

/index.js

Console

console

With Memoization

Let memoise the function. We can add a log object that our function will check everytime its called. If it finds a value for the input in the log, it will return that without needing to perform the calculation. If it doesn't, it performs the calculation, adds the result to the log, then returns the value. You can see in the console, the 3rd time we called the function (with the same input as the 1st call), no calculation was logged. Instead, the function just returned the value from the log.

/index.js

Console

console