Followers

Tuesday, December 6, 2016

Memoization in Python

Memoization is optimization technique that optimizes the number of calculations being performed by storing and reusing the already calculated values. A memoization cache is created when a function is called for the first time, and every time there is a call to the function, values are stored in the memoized cache, reducing the redundant calculations.

In the following paragraphs, the technique is illustrated using the example of a factorial.

A simple literal implementation of factorial in Python without using the recursion method is given by Figure 1:

 
Figure 1: Factorial using for loops


This case helps and gives the correct answer. This becomes redundant when there are many values whose factorials need to be calculated.

It is here that the technique of memoization comes handy. Figure 2 exemplarily illustrates the code for memoization technique.


Figure 2: Memoized factorial
If the values that are calculated are stored, then those values can be pulled from the memory for further calculations without recalculating again.
Figure 3 below illustrates a simple timer program that can calculate computational times for the two functions mentioned in Figure 1 and Figure 2 respectively.
 
Figure 3: Timer code for calculating computation times


On the first time call of the function, the normal factorial calculation illustrated by Figure 1 and the memoized factorial illustrated by Figure 2 utilize the same computational cycles and give results in the same time frame. For example, Figure 4 illustrates the code for calculation times for the the normal factorial calculation illustrated by Figure 1 and the memoized factorial illustrated by Figure 2 0.0395050048828 seconds and 0.0834770202637. In fact, this is quite in contrast with the expected results. 

Figure 4: Using timer from Figure 3 for doing calculations


However, if the calculations were repeated in this manner, the advantages of memoization come into picture. Figure 5 illustrated the example code for repeated calculations.


 
Figure 5: Repeated calculations


Using the code in Figure 5, when the computation times for the normal factorial calculation illustrated by Figure 1 and the memoized factorial illustrated by Figure 2 provide for 4.68964886665 seconds and 0.108646869659 seconds respectively.

This is primarily for the reason that once the factorials are calculated and stored and are retrieved when there is another instance for the variables. In the first case, the values get calculated every time and hence increase the computational times.

In this article, the benefits of memoization are explained. There is one disadvantage of memoization, that is, memory is used for storing the values. But that is a trade off that is to be balanced for gaining on the speed of computation.

Further, recursion methods give faster computation, that combined with memoized technique can make the programs a lot faster with a little trade off on memory. I will write more about those in another article.

There is my article on Memory optimization in Python.

No comments :

Post a Comment