JavaScript Memoization

Chris Hosler
Jan 22 · 4 min read
Image for post
Image for post
Credit: Clément Hélardot

Memoization is defined as “is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again”. To break this down, basically, what we want to do with memoization is try to speed up expensive function calls by caching previous results from the execution of the function call so that we are not performing the same calculations or operations over and over again.

Let’s take a look at a simple example, to start…

function addTo768(number) {
return number + 768;
}
addTo768(10); // Outputs 778addTo768(50); // Outputs 818addTo768(10); // Outputs 778

All we’re doing with the function addTo768() is adding whatever argument that we give the function by 768. So every time we call addTo768(), the function needs to perform number + 768, now given that this function isn’t really that expensive to call (or that this function really doesn’t have to do a lot of work), that’s not really that big a deal, and later on we’ll use a more expensive function but first let’s try to optimize this function using memoization. Earlier I said that memoization uses caching to improve performance, so in the case of our addTo768() function, what we want to do is set up a cache so that if we perform a calculation, that value is stored in our cache, and if we call the function again, if the value has already been calculated the function will return the cached value, as opposed to performing the entire calculation again.

So we could re-write our function to look like so…

function memoizedAddTo768() {
let cache = {};
return function addTo768(number) {
if (number in cache) {
return cache[number]
} else {
cache[number] = number + 768;
return cache[number];
}
}
}

If we look at the re-working of our addTo768() function, here we should be able to give the function a number, and it’ll either see if it has the answer stored in it’s cache or it will perform the calculation, give us that value, and store the result to it’s cache to recall later, if necessary. I should also point out that we created the cache as an object to store those values for us.

To use our new memoizedAddTo768() function, we do need to utilize a closure, if you’re not familiar with closures, I talked about them here, go ahead and read it we’ll wait…

Image for post
Image for post

You’re back? Great! Ok so now our full function call will look something like this…

function memoizedAddTo768() {
let cache = {};
return function addTo768(number) {
if (number in cache) {
return cache[number]
} else {
cache[number] = number + 768;
return cache[number];
}
}
}
let memoizedFunctionCall = memoizedAddTo768();memoizedFunctionCall(10); // Performs calculation, Outputs 778memoizedFunctionCall(10); // Calculation already performed, Outputs
cached 778

There you have it our new memoized function, now like I said, this function doesn’t have a whole lot to do, so it doesn’t use up a lot of memory or time, but let’s take a look at a more expensive function.

Let’s look at the good old Fibonacci sequence, where we want to start with either 0 or 1 (depending on who you talk to) and add the two previous numbers to get the next number in the sequence, so we’re looking to get…

FibNumbers = 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

We can create a function to do that right? Of course we can…

function FibSequence(n) {
if (n <= 1) {
return 1;
} else {
return FibSequence(n - 1) + FibSequence(n - 2);
}
}
FibSequence(5) // Outputs 8

The problem with this is that by using recursion, this function can be quite expensive to call, if you’re familiar with Big O notation, we’re looking at O(2^n), also we end up performing the same calculations over. If we look at FibSequence(5) we’re calling FibSequence(4) and FibSequence(3), who in turn call FibSequence() again, so our full function calls look like…

FibSequence(5) calls FibSequence(4) and FibSequence(3)
FibSequence(4) calls FibSequence(3) and FibSequence(2)
FibSequence(3) calls FibSequence(2) and FibSequence(1)
// Which ends up beingFibSequence(5)
FibSequence(4)
FibSequence(3)
FibSequence(3) // Repeated calculation
FibSequence(2)
FibSequence(2) // Repeated calculation
FibSequence(1)
Image for post
Image for post

That’s too much for me, let’s use memoization to optimize our function…

function memoFibSeq(n, cache) {
cache = cache ? cache : {};

if (cache[n]) {
return cache[n];
}

if (n < 2) {
return 1;
} else {
cache[n] = memoFibSeq(n - 1, cache) + memoFibSeq(n - 2, cache);
return cache[n];
}
}

memoFibSeq(5) // Outputs 8

This is a little bit more to break down but essentially we’re doing the same thing that we did above withmemoizedAddTo768(). In this case though, we added the cache as a argument to memoFibseq() so that it persists among function calls. Our memoized function now has a Big O notation of O(2n) which, again if you’re familiar with Big O, is better, but even if you’re not, it should make sense that by storing previous calculations and not having to repeat them over and over again, we should save time, the other side though is that by saving time we actually have to use more memory, as we have to save all of our cached values.

Well, there you go, that’s memoization in a nutshell. I hope that you found this helpful, and thanks for reading!

The Startup

Medium's largest active publication, followed by +773K people. Follow to join our community.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

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