Hello!
Today we will talk about Memoization as a caching technique. In recent interviews, I’ve been asked to solve a couple of questions related to caching, thus this newsletter.
What is 5*6?
What is 10*10?
Who is your president?
What is memoization?
Memoization and Idempotency
When you saw 5*6, did you manually calculate it? Or did it come from memory, off the top of your head? I could ask you “what is 5*6?” a million times and the answer will always be the same. This implies that the mathematical operation 5*6 is idempotent; the result will always be the same. Given that it is idempotent, it makes sense that we remember it off the top of our head, save ourselves some brain cells by not re-calculating it every time we are asked.
On the other hand, “who is your president?” depends on who and when you are asking. The answer changes, thus we’d need to update our memory every couple of years. I suppose a more interesting question would’ve been “who is your vice president?”
We can apply the same principle to programming when working with idempotent functions. A popular example used to explain memoization is the n-factorial (n!) problem. For those of us who do not remember, n-factorial is that math problem that requires you to multiply a number by all the numbers before it. Such that, factorial(3) is 1*2*3. Similarly, the factorial of 5 is 1*2*3*4*5. When you think about it, the factorial of 10 is 1*2*3*4*5*6*7*8*9*10. I wonder what the factorial of 11 is.
If you look at the factorial of 11, you will see that the only difference between that and the factorial of 10 is 11 itself. This implies that we solve the factorial of all numbers less than n while solving for the factorial of n. Below is the code for factorial(n).
const factorial = (n) => {
if(n===0) return 1
else return factorial(n-1) * n
}
factorial(11) => 1*2*3*4*5*6*7*8*9*10*11
factorial(10) => 1*2*3*4*5*6*7*8*9*10
When we call factorial with n=10, we calculate the factorial of 10 without considering that we already did the math for it while calculating the factorial of 11.
*Memoization walks in slowly and looks at the crowd*
let memoized = {}
const factorial = (n) => {
if(n===0) return 1
else if(memoized[n]) return memoized[n]
else {
let value = factorial(n-1) * n
memoized[n] = value
return value
}
}
Looking at the updated code, we see that we use an object (memoized) to remember the values we are calculating. Keep in mind that `memoized` can be named anything you want. If we see that a n has been calculated before, we do no recalculate it, rather we return its value from the memoized object; this saves us the effort of calculating it repeatedly when called.
A quick look at memoized when called with 11 is:
memoized: {
'1': 1,
'2': 2,
'3': 6,
'4': 24,
'5': 120,
'6': 720,
'7': 5040,
'8': 40320,
'9': 362880,
'10': 3628800,
'11': 39916800
}
As we can see, we memoized holds all the values for factorials 1…n. Future calls to the factorial function with n less than or equal to 11 won’t be recalculated. Calling factorial(10) should return an instant response using memoized since 10 had been previously calculated.
Conclusion
Memoization (caching in general) is useful in making slow processes faster by storing some data in-memory to prevent expensive recalculations. A good way to know when to use caching or memoization is if the result wouldn’t change if given the same input, meaning it is idempotent. There are, of course, techniques in caching that allows you to cache and invalidate caches in cases where the data changes “frequently” but that is beyond the scope of our discussion.
Well, I hope you’ve enjoyed reading this as I enjoyed writing it.
Adios!