Oi You! Stop Requesting Everything: A Simple Guide to Memoization
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 recognize when you should use memoization.
- To recognize when you should not use memoization.
Prerequisites
Although not necessary, this article will be better understood if you already have some knowledge of:
- Closures
- Higher order functions
- Pure functions
- Currying
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 initialize as an empty object. We also add the function which will be checking the cache, and 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.
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.
As you can see from the example above, we have a closure, memoizeFn, which initializes 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
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:
Here’s is our function, which looks very similar to our first example. Next, let’s see how we can use it.
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.
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 Summarize
- 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.
Originally published at https://dev.to on June 23, 2020.
