Memoize or Memorize? Memoize!
From Wikipedia “In computing memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.”
So basically, memoization is caching results of function calls. Obviously, this should be done ONLY for those functions which return the same result for same input.
It’s actually pretty easy to implement this. Let’s take a look at how we can implement this in a compute intensive function like calculating primes.
So let’s first write a simple prime program
As we can see, when the function is called twice for the same input, it goes thru the same numbers of execution cycles to compute whether it’s prime or not. What we can do is store the result for that number in some map and then return it without computing it again.
Here is modified isPrime with result caching.
As we can see, the second time we call isPrime with the same input, it returns the value from cache, saving time of executing the for loop. This is Memoization.
However, we would have to write our own code for Memoization every time. Can’t we build a standalone Memoization and “plug it” on different functions?
Of course we can!
Yay! We have created a “plug in” called memoize, which we can use to wrap any pure function (one which has no side effects and returns the same result for same inputs).
Wait a minute… if we call smartPrime with thousands of different values, won’t it eat up memory in the cache? Unfortunately, yes!