DEV Community

Kamlesh Nehra
Kamlesh Nehra

Posted on

Understanding Memoization In JavaScript

What is Memoization

Memoization is an optimization technique that speeds up applications by storing the results of expensive function calls and returning the cached result when the same inputs are supplied again.

Let's take an example, we have this method to calculate factorial of a number using recursion.

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

This function will work fine but in the long run, it will be expensive. let's say if it calls first memoFac(7) and then memoFac(8), Without a cache to store our previously calculated values, we have to repeat the entire process, returning the function another 7 times.

const cache = {}
function memoFac(n) {
  if (cache[n]) { return cache[n] } 
  else { 
    if (n === 0) { cache[n] = 1 } 
    else { cache[n] = n * memoFac(n - 1) } 
  return cache[n]
}

So we have another function memoFac() and global cache object which will store the result for that key.
Now, if we call memoFac(8) after we’ve called memoFac(7), we’ve already saved our calculated value for factorial(7) in our “cache” object, which has been moved outside of the function in order to retain its caching calculations. Thus, we only need to call the function once, calculate 8 * memoFac(7), which sends us straight to our “cache” to retrieve the cached value. Awesome!

But wait — if memoization follows the same general format (retrieving values from a cache in the outer scope of the function, or calculating the value using the anonymous closure function), couldn’t we write a general memoize function? Yes we can!

The concept of memoization in JavaScript is built majorly on two concepts.

  1. Closures
  2. Higher-Order Functions
function memoizerHoc(fun){
    let cache = {}
    return function (n){
        if (cache[n] != undefined ) {
          return cache[n]
        } else {
          let result = fun(n)
          cache[n] = result
          return result
        }
    }
}

Here we have HOC function memoizerHoc() and a local variable cache that can be accessible inside the returned function (closure).

Discussion (12)

Collapse
diogorodrigues profile image
Diogo Rodrigues • Edited

It's interesting.
But, how can I use the final function? I mean: how can I pass a recursive function as a parameter for memoizerHoc()? Could you provide an example invoking it?

And just to let you know, in the second example, you forgot to close the outer else. ✌

Collapse
unalo_baayriyo profile image
Kamlesh Nehra Author

Here is the example -
const multiplyTwo = (n) =>(n*2)
const memoizerHocMuultiplyTwo = memoizerHoc(multiplyTwo);
console.log(memoizerHocMuultiplyTwo(3)); // return calculated result
console.log(memoizerHocMuultiplyTwo(3)); // return cached result

Thanks for pointing out the missing bracket.

Collapse
diogorodrigues profile image
Diogo Rodrigues • Edited

Thank you!!! But in this case the examples are different, because in the first one you created a factorial of a number using recursion function. I didn't realize this difference before; I was thinking to pass a recursive function in the second example. Sorry for my bad.

Collapse
pentacular profile image
pentacular

The difficult problem with memoization is, as usual, cache invalidation.

Without this, it is simply trading space for time, and you might as well just use pre-computed tables which will have the added advantage of having an easily known memory cost.

Collapse
unalo_baayriyo profile image
Kamlesh Nehra Author • Edited

The memoized function is pure. A pure function will return the same output for a particular input no matter how many times it’s called, which makes the cache work as expected. If memory usage is a concern, then a fixed size cache should be used.

Collapse
xtofl profile image
xtofl

Conclusion: this particular, naive approach works best for

  • expensive functions
  • called more than once with the same arguments
  • but not too many different arguments (or tiny result types)
Collapse
unalo_baayriyo profile image
Kamlesh Nehra Author • Edited

Yes, Keep in mind that memoization does not make sense for all function calls. There is a higher memory overhead since we must store our cached results so that we can later recall them as well as an added complexity of using memoization, so it really only makes sense for functions that are computationally expensive.
Also, memoization does not work well for functions that are not pure, that is functions that have side effects. Memoizing only allows us to cache a result, so any other side effects get lost on successive calls.

Collapse
xtofl profile image
xtofl • Edited

Maybe an edge case... but for such generic higher order function, these are important, too.

function deeply_recursive(n){
  if (n > 1000000000) { return undefined; }
  return deeply_recursive(n+1);
}

Would it make sense to not use a potential return value as the clue whether something has been memoized?

Collapse
krzys1u profile image
Stożek Krzysztof • Edited

I have one question, let's say we have this recursive function

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

and we use this memo to do this:

const memoFactorial = memoizerHoc(recursiveFac);

console.log(memoFactorial(3));
console.log(memoFactorial(4));

function recursiveFac still will be called 7 times instead of 4 (result for free should be get from cache and use to count value for 4) ?

Collapse
unalo_baayriyo profile image
Kamlesh Nehra Author

It should be

const memoFactorial = memoize(
  (n) => {
    if (n === 0) {
      return 1;
    }
    else {
      return n * memoFactorial(n - 1);
    }
  }
);
Collapse
atellmer profile image
AlexPlex

I think here we need a mechanic of transformation any arguments to strings like JSON.stringify to save their in cache. Also memoization can lead easily to memory leak in real cases, so that I use this technic only for detecting last calculated value if I have too large objects as results of calculation.

Collapse
llagerlof profile image
Lawrence Lagerlof

Very interesting. One time I made the same thing for a expensive method call in a PHP application. I didn't knew this technique had a name. Thanks!