RSS

What is memoization??

31 Jul

               In computing, memoization is an optimisation technique used primarily to speed up

computer programs by caching the function results so that, later we can use that result,

when we call the function with the same arguments.

To explore memoization, lets consider the code segment for finding out the term of a  

Fibonacci series:

def fib(n):

     if n<2:return n

    else:

        n=fib(n-1)+fib(n-2)

    return n

Run the following command to find out the time taken for finding the nth term of the series

$ time python file_name.py

So we would find out then that the time complexity of  our program is O(exp(n)) .

Try and find out the 40th term of the Fibonacci series . This code segment will make you

wait for a considerable amount of time before you view your result in the terminal.

Is it possible to find out higher terms of the series much faster???

oh,yes!!

Here is the role of memoization.It caches the results that have been calculated earlier and

stores them in a lookup table so that these don’t have to be calculated again. We make use

of an associative array as a lookup table here.

The following code segment shows the memoized version:

table={0:0,1:1}

def fib1(n):

    if not n in table:

        table[n]=fib1(n-1)+fib1(n-2)

   return table[n] 

Run

$ time python file_name.py

Using this memoized function we would find out the higher terms of the series much faster.

But don’t forget everything has a reasonable limit

Advertisements
 
 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: