RSS

What is memoization??

               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

 
 
Aside

                    PYTHON is a high-level programming language which is used in thousands of

real-world business applications.It is an interpreted language. i.e. we can execute python 

programs by using an interpreter instead of a compiler.

The interpreter can be used for the execution of programs in any of the following two modes

  •    interactive mode :-interpreter reads and executes commands.
  •    script mode :-it reads and executes a script from a file.

Python’s interactive mode makes it easy to test short snippets of code.

To run python interpreter interactively, just type $ python in the terminal.

Before printing the first prompt(>>>),the interpreter prints a welcome message stating its

version number and a copyright notice as shown below .

Python 2.6.6 (r266:84292, Sep 15 2010, 15:52:39)

[GCC 4.4.5] on linux2

Type “help”, “copyright”, “credits” or “license” for more information.

>>>

The three right-angle brackets ,”>>>” is a python prompt indicating that the interpreter is

ready to use. One problem of the interactive mode is that , if we want to use them again the

next time,we have to type them all over again.So these definitions are stored in a separate

file ,called module or script and it is saved on disk.We can use this script later. Python files

have .py extension. For the execution of a script , the file name should be specified.

Basic Introduction