Oi you, stop making expensive function calls to request the same data you just retrieved 2 minutes ago! How, you ask? well that’s easy, using memoization of course.
Definition
Memoization is an optimization technique in dynamic programming, which involves storing the values of expensive function calls in memory, so that when you need to retrieve these values again, you can do so much, much quicker!
Aims
- To understand the basic concepts of memoization.
- To recognise when you should use memoization.
- To recognise when you should not use memoization.
Prerequisites
Although not necessary, this article will be better understood if you already have some knowledge of:
Overview
Memoization is a form of caching, which involves storing the return value of a function in memory. When the function is called, the cache object is checked to see if the value already exists for the input passed, if it does, then the cached result is returned. If it does not exist in the cache, then the heavy computation is done, and the returned value is also stored in the cache, to be retrieved quicker the next time it is needed.
Let’s take a look at a basic example...
Basic Example
1. Let’s create a closure
We use a closure to encapsulate our cache object, which we initialise as an empty object. We also add the function which will be checking the cache, and doing the heavy work.
const memoizeFn = () => {
// our cache object
let cache = {};
return (input) => {
// the contents of the function which will be doing the heavy work
}
}
2. Let’s create our function within the closure
In this example, we will be using a function which doubles the input, which is clearly not a high demanding function, but it serves for this example.
const memoizeFn = () => {
let cache = {};
return (input) => {
const result = input * 2;
return result;
}
}
3. Now, time to memoize
All we really need to do, is add an if..else condition in our inner function, to see if the value exists in the cache.
const memoizeFn = () => {
let cache = {};
return (input) => {
// lets log our cache here so we can see what is stored
// when we call our function
console.log(cache);
// have we got the result of this input already from a previous call?
if (cache[input]) {
// nice, we do! No need for any heavy computation here!
return cache[input];
} else {
// it’s not in our cache!
const result = input * 2;
// store the result in the cache so next time it is called with this input
// we can retrieve it from our cache
cache[input] = result;
return result;
}
}
}
As you can see from the example above, we have a closure, memoizeFn, which initialises our cache with an empty object, and returns a heavy computational pure function, which takes a number as an input. This input is used as our key in the cached object. Each time the function is invoked, the cache is checked to see if we already have a result for our input.
4. Let’s see it in action
// this invokes the first function and initialises our cache object
const doubleInput = memoizeFn();
doubleInput(10); // console log = {}
doubleInput(20); // console log = {10: 20}
// 10 is in our cache. No heavy computation needed
doubleInput(10); // console log = {10: 20, 20: 40}
The memoizeFn is invoked and assigned to the doubleInput variable, this variable can now access the cache object when it is invoked. First we call doubleInput with the value 10, at this point our cache object is empty, so the heavy computation of doubling this number needs to be done. Next, we pass 20 as our input, again, the this needs to run through the heavy computation section of the function as it does not exist in our cache. Finally, we pass 10 again to our function, the cache object is checked to see if a value with the key 10 exists, which it does, so the value is retrieved from the cache!
So, Where Would I Use This in the Real World?
Let’s take a look at a more real-world example. Say you are creating a SPA social media platform where a user can have a list of friends, and when the user clicks on one of their friends, it returns that user’s profile. We will need to call an API which returns the data related to that profile, right? Correct. But what if the user, as they are navigating round the website, returns to a profile they visited previously, do we want to call that API again? We could, or we could use memoization. Here’s how:
const memoizeUser = () => {
let cache = {};
return async (userId) => {
if (cache[userId]) {
return cache[userId];
}
// it's not in our cache, we need to hit the API
// this could take a little while...
const data = await fetch(`https://myapi.com/users/{userId}`);
const user = await data.json();
cache[userId] = user;
return user;
}
}
Here’s is our function, which looks very similar to our first example. Next, let’s see how we can use it.
// get access to the cache
const getUser = memoizeUser();
// add a click event listener to a button which gets a user’s profile
// this button will have an id of the users id that it accesses
document.querySelector('#getUserButton').addEventListener('click', async (e) => {
const userId = e.target.id;
// have we visited this user before?
const userData = await getUser(userId);
// rest of function which returns users profile using the
// userData retrieved above
});
when a users profile is clicked, we get the user id from the button, we then call getUser, which returns the users data. This will hit an API, unless we already have it in our cache from previously visiting this users profile, which in this case, the call to the server is not necessary, and we can get the data directly from the cache.
Simple, right? This covers the basics of memoization.
Time to Take it up a Notch
If you want to be really clever, you could even pass the heavy computational function to the closure itself, which could take a variable amount of arguments.
const memoize = (fn) => {
let cache = {};
return (...args) => {
// as this now takes variable arguments, we want to create a unique key
// you would need to define this hash function yourself
const key = hash(args);
if (!cache[key]) {
cache[key] = fn(...args);
}
return cache[key];
}
}
// some functions we can pass to memoize
const add = (num1, num2) => num1 + num2;
const subtract = (num1, num2) => num1 - num2;
// these 2 will have different cache objects thanks to closures
const add2Numbers = memoize(add);
const subtract2Numbers = memoize(subtract);
const result1 = add2Numbers(10, 20);
const result2 = add2Numbers(20, 30);
const result3 = subtract2Numbers(10, 5);
Pretty cool, right? We can define this memoize wrapper, and pass a number of functions to it, which each take a variable amount of arguments.
Some Do's and Don'ts
When can memoization be useful?
- When retrieving fixed data from an API.
- When performing demanding computation which may regularly reoccur for a given input.
When not to use memoization
- When retrieving data from an API whose data changes regularly.
- Simple function calls.
To Summarise
- Memoization is a form of caching, which stores the result of a demanding function.
- It is a simple technique which can be easily implemented in to existing code-bases to improve performance.
- Memoization is useful when dealing with fixed-data APIs, and regularly-occurring heavy computational functions.