Didn’t you wish there was an easy way to remember and retrieve those past results without having to recalculate the value every single time?Without Memo =(Memoization is an Optimization TechniqueIn programming terms, that’s all it really is.
It is a technique or practice which aims to increase a function’s performance by caching previous results.
Those values can be retrieved if they exist, otherwise the function will compute the new argument, return the results and cache it in a collection.
Whereby time is traded for space to boost cpu performance.
With the rise of functional programming in Javascript, it is more commonly used with recursive functions.
Since such functions can be load intensive.
Recursive function without memoizationLet’s take a look at this simple recursive function:const factorial = num => { // termination case if (num < 0) { throw new Error("Number must be positive.
"); }; // base case if (num === 0 || num === 1) { return 1; }; // recursive case return num * factorial(num – 1);};// Invoke the functionfactorial(3) // 6 factorial(4) // 24So we know that the factorial of the value 3 is 6, and 4 is 24, etc.
We know the factorial function works based on its argument and nothing else.
So ask yourself this: Would there be a performance hit if you had a large input value you had to compute many times? Is there a magic box somewhere someplace to store the result for each input to return if it was created some time ago in the past? How could we implement it for this scenario without relying on an external database?With Memo =)Memoize is a Special Higher Order FunctionLet’s write our memoize utility function to keep track of our results:const memoizeUtil = func => { // results store const cache = {}; return (input) => { // return the value if it exists in the cache object // otherwise, compute the input with the passed in function and // update the collection object with the input as the key and // computed result as the value to that key // End result will be key-value pairs stored inside cache return cache[input] || (cache[input] = func(input)); };};In the above code, all our results will be stored inside the cache object.
This would be the magic box that stores the results!Then using closure, we are able to either:A) Return the value if it exists in the cache where it is looked up by the input argument.
B) Otherwise, compute the input with the passed in function and update the collection object with the input as the key and the computed result as the value to that key.
The end result will be key-value pairs stored inside the cache.
Recursive Function with MemoizationNext in order to utilize our memoize function, what we have to do is wrap our factorial function into our memoize utility function so that it will be able to remember its past outputs:const findFactorial = memoizeUtil((num) => { // termination case if (num < 0) { throw new Error("Number must be positive.
"); }; // base case if (num === 0 || num === 1) { return 1; }; // recursive case return num * findFactorial(num – 1);})We can alternatively write the above in this fashion as well to stay organized:const findFactorial = memoizeUtil(factorial)function factorial(num) { // termination case if (num < 0) { throw new Error("Number must be positive.
"); }; // base case if (num === 0 || num === 1) { return 1; }; // recursive case return num * findFactorial(num – 1);}Invoke our wrapped factorial function from above to find the results:findFactorial(2) // 2findFactorial(3) // 6findFactorial(6) // 720// Current cache object with stored values: {2: 2, 3: 6, 6: 720}findFactorial(6)// Returned value from cache object: 720findFactorial(5) // 120// Current cache object with stored values: {2: 2, 3: 6, 5: 120, 6: 720}Test Memoization by Performance:console.
time('factorial test no memo');findFactorial(6) // 720console.
timeEnd('factorial test no memo');factorial test no memo: 0.
110ms–console.
time('factorial test with memo');findFactorial(6) // 720console.
timeEnd('factorial test with memo');factorial test with memo: 0.
019msAs you can see from the above, there is clearly a speed performance by using this special technique.
Let’s test this further by inputting a larger value to calculate:console.
time('factorial test no memo');findFactorial(100) // 9.
33262154439441e+157console.
timeEnd('factorial test no memo');factorial test no memo: 0.
264ms–console.
time('factorial test with memo');findFactorial(100) // 9.
33262154439441e+157console.
timeEnd('factorial test with memo');factorial test with memo: 0.
021msAgain, the performance gain is clear and its benefits truly shine the larger your calculations become / the larger your stack in a recursive call.
While the computational times may vary somewhat across a range of computers, the gain will still exist.
Console.
log TestIn a separate test where I did console.
log for the return value of findFactorial(100) — It took a whopping 2~4 seconds without memoization and averaged 100~300 milliseconds with memoization.
That’s crazy!ConclusionAfter implementing memoization to the recursive factorial function, you’ll notice not much has changed and it mostly still works like the original.
Though now from the perspective of performance, it runs much faster than without using memoization using repetitive inputs.
Though remember that this technique should only be applied to pure functions which have no side-effects (versus impure functions), so results are more predictable.
Since the point of memoizing is storing data in memory with a look-up table so it can be access at a later point, the advantages are noticeable for load intensive computations.
What else could you do if you had more than one argument?.What if you wanted to memoize the recursive Fibonacci sequence?.Give it a try!.. More details