I’ve been going through Ruby Best Practices book lately and, while it covers a lot of interesting topics, one thing caught my eye. It was sub-chapter about memoization.
Memoization is an optimization technique used to speed up your programs by avoiding to repeat function calls for already calculated inputs. Example in the book was a simple Fibonacci sequence program written with and without memoization. It was really shocking for me to see how big of an advantage memoization gives you. I rewrote the examples and made some benchmarks to see the actual results and improvements.
Here is a simple Fibonacci implementation in ruby:
Calling this function for larger inputs is not a good idea because for input 30 calculation lasts for 3 seconds, and it increases exponentially.
Simple benchmark for this function made using benchmark:
Using memoization for generating Fibonacci sequence means we are not going to calculate solutions for inputs we have already calculated. For Fibonacci sequence, this is an enormous gain in performance.
Simple implementation of fibonacci using memoization:
With memoization, calculations for inputs like 30, 40 etc. are done instantaneously. Memoization also enables us to calculate values for inputs like 1000, 2000 etc. For example,
So, to summarize, using memoization you can speed up your programs by storing already calculated results in an array (or hash). This speed gain comes with a price. You need extra memory to hold all of the calculations, and for larger inputs you would need a lot of it.
Also there is this thing called SystemStack. And it can exceed its maximum depth fairly easy. For example, I get for very big numbers (> few thousands)