May 14, 2019

Algorithms with Javascript: Memoization

Algorithms with Javascript: Memoization

In this short article I want to talk about on how to optimize expensive operations in Javascript. Memoization is just caching values by returning them from function calls. In Javascript we can make use of closures to create generic functions with memoization.

Instead of calculating a value or making some api call over and over again, we can make use of an object that works as cache. The following simple example shows the basic functionality of memoization. We make use of the json-placeholder api, which is free to use.

const cache = {};
const url = "https://jsonplaceholder.typicode.com/comments/";

const fetchComment = (id, cb) => {
    if (cache[id]) {
        console.log("FROM CACHE");
        cb(cache[id]);
        return;
    }
    
    fetch(url + id)
        .then(res => res.json())
        .then(json => {
           cache[json.id] =json;
           cb(json);
        })
        .catch(err => err);
}

fetchComment(1, comment => {
    console.log(comment);
});

setTimeout(function() {
  fetchComment(1, comment => {
    console.log(comment);
  });
}, 500)

Explanation: In the global scope we define a cache variable with an empty object followed by the url for the json-placeholder api. Next we define a function that takes two arguments, first an id we need to associate the comment we want with and a callback function we need to call, since fetch returns a promise.

Within the fetchComment function we check if there is already a comment with the id saved, if that turns out to be true we pass in the cached value into our callback function and then return nothing to end the function call.

If there is no value found in the cache with that id, we fetch it from the api and then save it to the cache before calling our callback function with the JSON response. We later call the fetchComment function twice, the second time we use the setTimeout function since we make an async request. Instead of fetching the comment with the id one now all over again, our function will look in our cache and then return its value, that speeds up our software immensely.

But in this example we did something we should not do, we declared out cache globally. The next step is now to make use of closures, so we return a function within a function that has access to the parent functions scope. Let's have a closer look at that.

const fetchComment = () => {
  const cache = {};
  
  return (id, cb) => {
    const url = "https://jsonplaceholder.typicode.com/comments/";

    if (cache[id]) {
      console.log("FROM CACHE");
      cb(cache[id]);
      return;
    }
    
    fetch(url + id)
      .then(res => res.json())
      .then(json => {
        cache[json.id] =json;
        cb(json);
      })
      .catch(err => err); 
  }
}

const getComment = fetchComment();

getComment(1, comment => {
    console.log(comment);
});

setTimeout(function() {
  getComment(1, comment => {
    console.log(comment);
  });
}, 500)

As you can see, we moved our cache declaration into the fetchComment function. Then we return another function that takes the same two arguments as the fetchComment function did before, the rest is the same.

So what happens now when we assign the function call of fetchComment to our variable getComment? It will return the function definition of our function within fetchComment and this function will have access to cache and also to the arguments we pass in when we call getComment. When we now call getComment, we call:

return (id, cb) => {...}

We now have the same memoization as before but we do not pollute the global scope with our cache.

>>> Check out my Udemy courses.