What's memoization
In programming, memoization is an optimization technique that makes applications more efficient and hence faster by storing computation results in cache, and retrieving that same information from cache the next time it's needed instead of computing it again.
In simpler words, it consists in storing in cache the output of a function, and making the function check if each required computation is in cache before computing it.
A cache is simply a temporary data store that holds data so that future requests for that data can be served faster.
Memoization is a simple but powerful trick that can help speed up our code, specially when dealing with repetitive and heavy computing functions.
How does it work?
The concept of memoization in JavaScript relies on two concepts:
- Closures: The combination of a function and the lexical environment within which that function was declared.
- Higher Order Functions: Functions that operate on other functions, either by taking them as arguments or by returning them.
If you're not familiar with these two concepts, we'll clarify with an example in a little bit. Also, I have articles on closures and Higher order functions that might help you. ;)
A classic example
To clarify this mumbo jumbo, we'll use the classic example of the fibonacci sequence.
The Fibonacci sequence is a set of numbers that starts with a one or a zero, followed by a one, and proceeds based on the rule that each number (called a Fibonacci number) is equal to the sum of the preceding two numbers.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
Let's say we need to write a function that returns the nth element in the fibonacci sequence. Knowing that each element is the sum of the previous two, a recursive solution could be the following:
const fib = n => {
if (n <= 1) return 1
return fib(n - 1) + fib(n - 2)
}
If you're not familiar with recursion, It's simply the concept of a function that calls itself, with some sort of base case to avoid an infinite loop (in our case if (n <= 1)). Again, I have an article on recursion if you're interested. ;)
If we call our function like fib(5), behind the scenes our function would execute as following:
See that we're executing fib(0), fib(1), fib(2) and fib(3) multiple times. Well, that's exactly the kind of problem memoization helps to solve. With memoization, there's no need to recalculate the same values once and again, we just store each computation and return the same value when required again.
A memoized version
With memoization implemented, our function could look like this:
const fib = (n, memo) => {
memo = memo || {}
if (memo[n]) return memo[n]
if (n <= 1) return 1
return memo[n] = fib(n-1, memo) + fib(n-2, memo)
}
What we're doing first is checking if we've received memo object as parameter. If we didn't, we set it to be an empty object:
memo = memo || {}
Then, we check if memo contains the value we're receiving as param within it's keys. If it does, we return that. Here's where magic happens. No need for more recursion once we have our value stored in memo. =)
if (memo[n]) return memo[n]
If we don't have the value in memo yet, we call fib again, but now passing memo as parameter, so the functions we're calling will share the same memoized values we have in the "original" function. Notice that we add the final result to the cache before returning it.
return memo[n] = fib(n-1, memo) + fib(n-2, memo)
And that's it! With two lines of code we've implemented memoization and significantly improved the performance of our function!
If my article was helpful, consider inviting me a coffee = )
