The 2:00 AM Javascript Blog About: Memoization!

I’m exhausted. And that’s why I’m cheating: it’s only 2:15. You’ll have to forgive me. I am actually on a short vacation with my wife and it’s been a calorie-laden, fun packed day that has left me wiped. All that is left is for me to “cache” some z’s… Oh, MAN am I in prime form tonight!

Ok. Let’s get down to business so I can drift off to what I am sincerely hoping is going to be great sleep.

As always, I don’t claim to have the best, or only solution, just one that I hope adds understanding.

With that in mind:

What is Memoization?

Well, let’s say you have a function that is being called in your code over and over again. Perhaps it’s a nasty little recursion problem, a mathematical function, or something of a similar nature. Regardless, you’ve been calling this function multiple times, sometimes even with the same arguments. All of those calls add up, and they become expensive, slowing down your code and making life much less fun. We don’t like that. So what do we like? Clean, fast, efficient code!

How do we get there? Memoization! Memoization essentially is the process of creating a “cache,” or storage, for the results of these expensive calls so that if we ever need to call the function yet again, we can now first quickly run a check over an object that might contain a value from the last time you went through this function. Here are a couple examples of where this might come in handy:

Let’s say you are asked to do the recursive solution for the calculation of factorials for a certain number: for recurseFac(4) you would get 4*3*2*1. Being an amazing coder, you write out a recursive solution:

function recurseFac(n) {
if(n == 0) return 1
return n * recurseFac(n-1)
}

This might look great for a simple recursive sample problem, but what if, for some weird reason, you needed to do recurseFac(200)? Now imagine calling that function multiple times in your code! That is quite nasty to think about! Wouldn’t it be nice if there was some way to store the computed value from last time and there would be an easy way to get an answer without all the function calls annihilating our poor stack?? Even if the value passed in were, for example, 201, instead of 200, we could leverage our previous answer, since the function will hit our lookup at recurseFac(200) (which was already stored) instead of having to do all the calculations again!

recurseFac(200) (which is cached, so just a lookup) * 201

That would be so nice!

Luckily, we have the memoization technique! It will cache the result of one such call, so that next time we won’t have to go through the pain and annoyance of doing it again!

Before I show you a quick, not-too-difficult and reusable way to accomplish this, let’s run through another famous example where memoization is an effective tool in speeding up our function calls: the recursive fibonacci problem.

Here’s what the tree looks like for the classical solution for fibonacci sequences using recursion:

function recurseFib(n) {
if(n < 2) {
return n
}
return recurseFib(n-1) + recurseFib(n-2)
}

Fibonacci Recursion Tree

As you can guess, the fact that we needlessly make calls with the same argument is not ideal. In fact, it would be optimal to avoid needing to do so at all. By using the memoization technique, we store a key value pair with the value of the result of the function. This allows us to dramatically reduce the time each call takes to run fully.

So, how do we do it? Well, here is one way, which is reusable and pretty clean, if you ask me:

Let’s work through it:

1. Since we want to reuse this memoize function for any future functions that fit the criteria, this memoize function will presumably take a function parameter.
2. We must return a function that takes a potentially unlimited amount of arguments (…args, anyone?). This is because whatever function we want to memoize will have a variable amount of arguments: we don’t know ahead of time how many arguments there will be! We must also make sure our cache object is in the outer function, so that closure takes care of persisting the cache throughout all of our calls.
3. We must ensure that the function runs with all of the passed arguments, but only if the cache is empty.

Before we actually code this, let’s run through a quick refresher:

The ‘…args’ that i mentioned above is called the spread operator

Let’s see this in code:

function memoize(funcToCache) {
 const cache = {}; //create the cache, using closure to keep it around.
 return function(…args) { //this is the inner function that will run only if our cache is empty.
 if(cache[args]) {
 return cache[args] //check if the arguments have ever been used before, in which case the result of such a call is in cache, and should be returned. 
 }
 let result = funcToCache.apply(this, args); //if nothing is found in cache, run the function with it's regular prescribed arguments.
 cache[args] = result;
 return result //don't forget the returning of the result, and the adding to cache! Good stuff.
 }
}

Whew! Ok, lotta code, but the concept is mainly this: make an object that sticks around and keeps results of previous calls to functions that are otherwise expensive. Then, allow our expensive function to run only if we have already checked our object and come up with nada. Cool!

Oh, and as an aside(another reminder: make a post about call, apply, and bind): we are using .apply, which will set the context of the function via the first argument, and pass it an array of items to work with as arguments via the second argument. More on that, as I said, in another post.

So now that we have this memoization function, let’s apply it (seriously, no pun intended) to the examples from above:

Taking the recurseFac, we would set recurseFac itself equal to memoize(recurseFac). This is crucial in order to avoid naming confusion: try to set the name of the function to your new, memoized function rather than using different names, because, as I will show you in a second, it might get ugly if you don’t, leading you to call the wrong function.

So we would say recurseFac=memoize(recurseFac) and then make our call as usual. Now, we check the cache before making unnecessary operations.

For the fibonacci, we would do the exact same thing: recurseFib = memoize(recurseFib), and call as regular.

So why then do the names matter? Well, if you don’t rename the function, or ensure that the recursive calls at the bottom of your recursive function reference your new, memoized function, you will not have accomplished anything, and your efficiency will not have improved!

Final point: make sure your memoized function is ‘pure,’ meaning it returns the same output if the input is the same, no matter how many times the function is called. It won’t work otherwise!

So there are benefits. Any drawbacks?

Well, actually, yes, glad you asked! Why would someone not want to use memoization?

Perhaps one answer is when there are a lot of values to keep track of, and the calls reaching these exact values don’t happen very often. The memory expensiveness of storing all these results would not be worth the benefit of potentially avoiding a recursive call.

Another, more involved drawback, is the fact that objects cannot take instances of other objects as keys, so this function will only work if the keys we are passing are not objects. If we try, Javascript won’t differentiate between the objects because when we pass them in as keys, the ‘toString’ prototype method is run and the key will end up being ‘[object Object],’ which is the result of that toString invocation regardless of the origin object’s keys and values. Not good. Check out my colleague Elana’s post on this for a succinct, in depth analysis on this topic: https://medium.com/@elanamig/object-friendly-cache-in-javascript-e686aa19451f

Otherwise, this has been fun! Like I said, by far not the only way to do it, just wanted to perhaps demystify this concept for some. Hope it did, and shoot me any thoughts/q’s (but not at 2am. You’d have to be crazy to be up and writing about Medium coding posts at that hour).