Memoization for the functional programming
Memoization, storing something in the memory, is very important in the functional programming to avoid repetitive calculation. Such process, sometimes can be used as the cache mechanism, can save a lot of time, since the memory can be used as containers for expansive calculations or slow I/O results. Yesterday I read a magic Ruby trick to realize the memoization and would like to try here:
See, when the new hash is declared here, the hash value is calculated only to the previous 1 or 2 elements. Since most of the calculation results are stored in the hash, the complexity of calculating Fibonacci here is only
O(n), or even less if repeat. However, using recursive to to calculate Fibonacci will get much higher
O(2^n) for each calling, what a difference! Another cool way is to utilize Ruby's
Fiber class since it 'freezes' upon yield, shown in Mat's The Ruby Programming Language
What does it compare to conventional looping method? You would think? Well, for new calculations, a looping method calculating Fibonacci also gets the complexity of
O(n) as well, but if more calculations on the way, the stored results in the memory will function as the cache and less processor power or time will be needed, compared to the looping without memoization shown below.