How to Implement JavaScript Memoization from Scratch
Before we talk about memoization, let’s understand how values are commuted in a computer.
Let’s say we have a function that adds up two number. If we have a program that calls this function 50 times with the same input, we would be doing a lot of unnecessary calculations.
Enter memoization.
Memoization is an optimization technique used to speed up computer programs by storing results of function calls and without having to re-compute assuming the parameters and variables to make the function call is same.
Let’s take a look at the following:
Notice ‘computed result’ will only be computed when the result is not memoized. If memoize function works as expected, then addFunc will only be called once and any call of memoizedFn after that will return a result that has already been stored in memory.
Let’s take a look at the implementation of memoizedFn:
I know this is a bit lengthy but here is how we can look at. We have a memoizedResults that caches all the results that have been computed.
For example, if we pass in addNumber as a parameter when the user calls the memoized function, it first checks if the function definition is available in the memoizedResults. If it is, we take the result that was cached by referencing memoizedResults[func].result.
Let’s say we have cached the result. We still have to check if the arguments have changed. Imagine if we call addNumber(1,2,3). That’s fine, we will store addNumber as a key in the memoizedResult with a result field of 6 and args that contains 1,2,3. What if we call addNumber(3,4,5). Sure, we have stored the result of memoizedResult but if we use the cached result then addNumber(3,4,5) won’t return the right result.
Well then, how do we make sure we are using cached results properly, and when to recalculate the result as needed?
Let’s say if we set memoizedFn to be addNumber for the first time and we called memoizedFn(1,2,3) for one time. For the first time, we will store args along with the func name into the map. When we call memoizedFn(3,4,5), we call getArgKeysFromMemoized and getArgValsFromMemoized to check if the arguments we memoized is same as the arguments that were passed in on the latest function call. In this case, if they are not the same, we recompute the result and again memoize them into our map. At the end, we simply return the result from the map.
Let’s ask ourselves this question: why memoization? Earlier we did say about getting some piece of data for 50 times but is that really a problem?
Yes, it can be.
What if these data contain million and billion of rows of data? If we memoized it then we won’t have to retrieve those datas unless it is needed. Imagine having an application that makes an api call to grab a million rows of items and storing them locally in the memory. If we implement a powerful memoization mechanism, we can check if these data got changed before having necessity to grab the most updated data.
Remember, every action to get the api saved is every million of data that we do not need to get. This, in some cases, can be the difference between having a fast and efficient application versus an application that cannot function properly due to the amount of data getting retrieved.
More content at plainenglish.io
