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.

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.

*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.*

*er from Figure 3 for doing calculations*

*Figure 4: Using tim*

*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.*

*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