JavaScript: Memoization

What memorization is, and a simple example of it using a Hash. Super easy. Don’t worry. We will put this behind you.

Sometimes, a function can become expensive to call multiple times. It be like that.

What does that mean? It means if we call a function multiple times when we already have its result from a previous run, we shouldn’t need to process the resulting value again.

But we can skip running it again if this function is pure. Like pure water. Kidding. A pure function always returns the same output given the same input. So if I give it an input of 2, it will always give me 10, no side effects, no API calls, no randomness. If that’s the case, we can memoize it.

Going over to Wikipedia to explain this creepy word:

Memoization 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

So it seems like we need to store the previous results of previous runs somewhere. But we can’t do that inside the function, because the function’s local scope, will not have the ability to remember what it ran before.

function calculateSomethingCrazy(n) {
 // how do i remember my previous values
 // complex operations 
 return result;
}

We can do this using a closure. Ummm.. okay closures need their own article. Please read my article here. I promise it’s only ~5 mins. If you don’t understand closures, it will be difficult to proceed.

So we know with a closure, we can wrap an outer function around an inner function, and when we do this our inner function can remember things. It can have a living breathing memory.

function memoizedCalculation () {
  // place our memories here
  let cache = {}; 
  function calculateSomethingCrazy(n) { 
   // complex operations
   // check cache
   return result;
  }
  return calculateSomethingCrazy; 
}
let memoizedCalculationFunction = memoizedCalculation();
memoizedCalculationFunction(1); // updates cache
memoizedCalculationFunction(2); // updates cache
memoizedCalculationFunction(3); // updates cache

So there’s a little spot there, in the wrapper where we can put variables and we put our cache there. Every time calculateSomethingCrazy runs, it can store its results in the cache.

We return calculateSomethingCrazy(), again this is a closure way of doing things. And we save the result in a variable. So we can run the function whenever we desire.

This function isn’t like any other function, it has a backpack of memories. Formed with the closure.

OK now in our function, we can reference this hash before running our complex operations. If we have already run this function with the input n before, we already know that value, so we just return it from the cache.

But if we haven’t, we run the complex operations and save it to the hash for later retrieval.

Remember, a hash is an easy lookup object, where our index/key can be the input we receive to the function, and the value can be the result. So if we want to grab an item from the cache it’s as simple as cache[n]. We don’t need to search an array for it to see if it exists.

if (n in cache) {
      console.log('Fetching from cache');
      return cache[n];
    }
    else {
      console.log('Calculating result now');
      let result = n + 10;
      cache[n] = result;
      return result;
    }
 }

Ok all together now:

function memoizedCalculation () {
  // place our memories here
  let cache = {};
  function calculateSomethingCrazy(n) {
    if (n in cache) {
      console.log('Fetching from cache');
      return cache[n];
    }
    else {
      console.log('Calculating result now');
      let result = n + 10;
      cache[n] = result;
      return result;
    }
  }
  return calculateSomethingCrazy;
}
let memoizedCalculationFunction = memoizedCalculation();
// Run the function with different inputs
memoizedCalculationFunction(1); // calculates and updates cache
memoizedCalculationFunction(2); // calculates and updates cache
memoizedCalculationFunction(2); // retrieves value from cache

Ok, so what are the problems with memoization

• Memoizing is a trade-off between space and speed. As you can see we are allocating new memory for this cache. But at the same time, we are improving the speed of our function
• We shouldn’t use memoization for API calls, or functions that aren’t pure

Tanks for reading friends!