loading...

Understanding Memoization In JavaScript

unalo_baayriyo profile image Kamlesh Nehra ・2 min read

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).

Posted on by:

unalo_baayriyo profile

Kamlesh Nehra

@unalo_baayriyo

Javascript, React, Node Js

Discussion

pic
Editor guide
 

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. ✌

 

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.

 

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.

 

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.

 

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.

 

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)
 

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.

 

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?

 

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) ?

 

It should be

const memoFactorial = memoize(
  (n) => {
    if (n === 0) {
      return 1;
    }
    else {
      return n * memoFactorial(n - 1);
    }
  }
);
 

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.

 

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!