What is Memoization?

If you can get past pronouncing that correctly, keep reading further to figure how what it is. Memoization is a great tool for improving the runtime of large complex applications by storing or caching previous results so they can be called upon if the algorithm is run again with the same inout. It can turn functions that are very complex into very efficient ones, and it’s skill that programmers should know about.

In order to see how memoization comes into play, consider the following JavaScript function that takes in a number and squares it:

function square(n) {
 let result = 0
 for (let i = 1; i <= n; i++) {
  for (let j = 1; j <= n; j++) {
   result +=1
   }
  }
 return result
}

Ok, the first thing you might notice is that this function is incredibly inefficient. That’s only for example purposes. This function is going to take a long time time to run when we start inputting large numbers, that runtime may only be half a second or so, but in programming standards, that time starts to add up. Especially when you think of that gargantuan software applications that exist out there. Also think about is we had to call this function multiple times over with the same large input. Longer and longer runtimes.

This is where we can use memoization to cache the previous results. That way if this function has run with the same input as before, we can get the results instantaneously. To employ memoization, we can adjust our function to include the following:

const previousResults = []
function square(n) {
 let result = 0
 for (let i = 1; i < n; i++ {
  for (let j = 1; j < n; j++ {
   result +=1
   }
  }
 previousResults[n] = result
 return result
}

We start by creating an array to store all the previous results so that anytime we run this function, the value of ‘result’ gets stored in the array. Right now, the runtime for multiple calls will still be very slow, we’d to first check to see if this function has been called before with the same previous input:

const previousResults = []
function square(n) {
 if (previousResults[n] != null) {
  return previousValues[n]
 }
 let result = 0
 for (let i = 1; i < n; i++ {
  for (let j = 1; j < n; j++ {
   result +=1
   }
  }
 previousResults[n] = result
 return result
}

That opening if statement is the key to making memoization work. We check the array to see if the result of a previous function call is already there and if it is, simply return in instead of running the entire function.

This is a great example of how to employ memoization, but as previously pointed out, the function was inefficient to begin with, so let’s take a look at another example.

Memoization works very well with recursive functions, which is where a function will call itself until a certain condition is met. With a function calling itself, being able to store the previous results will help improve the complexity. Let’s take a look a at the Fibonacci sequence, where the next number is the sum if the two previous numbers.

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...]

If we wanted to build a recursive function to determine the nth number if the sequence, it might look something like this:

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

Now this is inefficient, but not purposely so, this will take longer and longer to run as the value of ’n’ increases. You might notice that in the function calling itself over, we will be calculating using similar inputs. We can use memoization to speed up this process, this time I will memoize using a separate function:

function memoize(fn) {
 previousValues = {}
 return function(...args) {
  if (previousValues[args] {
   return previousValues[args]
  }
 const result = fn.apply(this)
 previousValues[args] = result
 return result
}
function fib(n) {
 if (n < 2) {
 return n
}
 return fib(n - 1) fib(n - 2)
}
fib = memoize(fib)

This is a bit more of a generic approach to memoization but the same concepts apply. Once we run the fib function. Our result will be stored somewhere, in this case it’s the object seen above. The first thing that happens is we check the object to see if there’s anything in there, and if so return it. Only when the function sees that it hasn’t been run with the new input will it run in its entirety, but then the result will be stored for next time.

Memoization may be hard to pronounce but its extremely helpful with dynamic programming and complex algorithms. It’s a tool that programmers should know about for building applications or simp’y preparing for your next technical interview!