What is Memoization in Javascript?

The basis of memoization and a simple use case implementation

Have you ever had to write a pure function where it had to calculate the same input multiple times on different occasions? Didn’t you wish there was an easy way to remember and retrieve those past results without having to recalculate the value every single time?

Without Memo =(

Memoization is an Optimization Technique

In programming terms, that’s all it really is. It is a technique or practice which aims to increase a function’s performance by caching previous results. Those results can be retrieved if they exist, otherwise the function will compute the new argument, whose new results will be cached into a collection. Whereby time is traded for space to boost cpu performance.

With the rise of functional programming in Javascript, it is more commonly used with recursive functions. Since such functions can be load intensive.

Recursive function without memoization

Let’s take a look at this simple recursive function:

const factorial = num => {  // termination case
if (num < 0) {
throw new Error("Number must be positive.");
};
// base case
if (num === 0 || num === 1) {
return 1;
};
// recursive case
return num * factorial(num - 1);
};// Invoke the function
factorial(3) // 6
factorial(4) // 24

So we know that the factorial of the value 3 is 6, and 4 is 24, etc. We know the factorial function works based on its argument and nothing else. So ask yourself this: Would there be a performance hit if you had a large input value you had to compute many times? Is there a magic box somewhere someplace to store the result for each input to return if it was created some time ago in the past? How could we implement it for this scenario without relying on an external database?

With Memo =)

Memoize can be a special Higher Order Function

Let’s write a memoize utility function to keep track of our results:

const memoizeUtil = func => {  // results store
const cache = {};
return (input) => { // return the value if it exists in the cache object
// otherwise, compute the input with the passed in function and
// update the collection object with the input as the key and
// computed result as the value to that key
// End result will be key-value pairs stored inside cache
return cache[input] || (cache[input] = func(input)); };
};

In the above code, all our results will be stored inside the cache object. This would be the magic box that stores the results!

Then using closure, we are able to either:

A) Return the value if it exists in the cache where it is looked up by the input argument.

B) Otherwise, compute the input with the passed in function and update the collection object with the input as the key and the computed result as the value to that key. The end result will be key-value pairs stored inside the cache.

Recursive Function with Memoization

Next in order to utilize our memoize function, what we have to do is wrap our factorial function into our memoize utility function so that it will be able to remember its past outputs:

const findFactorial = memoizeUtil((num) => {  // termination case
if (num < 0) {
throw new Error("Number must be positive.");
};
// base case
if (num === 0 || num === 1) {
return 1;
};
// recursive case
return num * findFactorial(num - 1);
})

We can alternatively write the above in this fashion as well to stay organized:

const findFactorial = memoizeUtil(factorial)function factorial(num) {  // termination case
if (num < 0) {
throw new Error("Number must be positive.");
};
// base case
if (num === 0 || num === 1) {
return 1;
};
// recursive case
return num * findFactorial(num - 1);
}

Invoke our wrapped factorial function from above to find the results:

findFactorial(2) // 2
findFactorial(3) // 6
findFactorial(6) // 720
// Current cache object with stored values:
{2: 2, 3: 6, 6: 720}
findFactorial(6)
// Returned value from cache object: 720
findFactorial(5) // 120
// Current cache object with stored values:
{2: 2, 3: 6, 5: 120, 6: 720}

Test Memoization by Performance

We can run a timer by utilizing console.time() and console.timeEnd() and wrapping the desired function call between the two. Let’s take a look:

console.time('factorial test no memo');
findFactorial(6) // 720
console.timeEnd('factorial test no memo');
factorial test no memo: 0.110ms--console.time('factorial test with memo');
findFactorial(6) // 720
console.timeEnd('factorial test with memo');
factorial test with memo: 0.019ms

As you can see from the above, there is clearly a speed performance by using this special technique. Let’s test this further by inputting a larger value to calculate:

console.time('factorial test no memo');
findFactorial(100) // 9.33262154439441e+157
console.timeEnd('factorial test no memo');
factorial test no memo: 0.264ms--console.time('factorial test with memo');
findFactorial(100) // 9.33262154439441e+157
console.timeEnd('factorial test with memo');
factorial test with memo: 0.021ms

Again, the performance gain is clear and its benefits truly shine the larger your calculations become / the larger your stack in a recursive call. While the computational times may vary somewhat across a range of computers, the gain will still exist.

Console.log Test

In a separate test where I did console.log for the return value of findFactorial(100) — It took a whopping 2~4 seconds without memoization and averaged 100~300 milliseconds with memoization. That’s crazy!

Conclusion

After implementing memoization to the recursive factorial function, you’ll notice not much has changed and it mostly still works like the original. Though now from the perspective of performance, it runs much faster than without using memoization using repetitive inputs.

Though remember that this technique should only be applied to pure functions which have no side-effects (versus impure functions), so results are more predictable. Since the point of memoizing is storing data in memory with a look-up table so it can be access at a later point, the advantages are noticeable for load intensive computations.

What else could you do if you had more than one argument? What if you wanted to memoize the recursive Fibonacci sequence? Give it a try!

Software Engineer

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store