Memoization :

Memoization is a technique for remembering the results that incur huge costs to running time to the algorithm.

Memoization in python is generally carried out using dictionary(hash) data type.

Memoization technique is simpler than it sounds.

A brief idea using example:

Let's take example of factorial function : 

'Native way : '
 

def fact(n):
    if n in [0, 1] : return 1
    else : return n*fact(n-1)

This is what we use generally for computing factorial.

Let's compute factorial for first 5000 natural numbers and calculate time:

'Native way : '
from time import time
def fact(n):
    if n in [0, 1] : return 1
    else : return n*fact(n-1)
start_time = time()
for i in range(5000):
    fact(i)
end_time = time()
print("Time required :", end_time-start_time)

Output :

Time required : 12.179325103759766

This computation took 12 secs in my OS!!

This may be lesser for you, but it is still a big time.

This is because, at every integer n, it  recursed for n-1 times.

Memoization does a smart move here.

Memoization says that, when you know that the result that you got will be used later on, why dont you store it??

Hence, in program, we will store value of computed value at each step.

memory = {}  # a dictionary storing n : fact(n)
def fact(n):
    try : return memory[n]
    except:
        "compute"
        if n in [0, 1] : return 1
        else :
            memory[n] = n*fact(n-1)
            return memory[n]

In this function, we have used try except:

try checks if key n is present in our memory dictionary.

If it is not present, it is computed, stored and returned.

Let's test it for its time complexity :

'Memoized '
from time import time
memory = {}  # a dictionary storing n : fact(n)
def fact(n):
    try : return memory[n]
    except:
        "compute"
        if n in [0, 1] : return 1
        else :
            memory[n] = n*fact(n-1)
            return memory[n]
start_time = time()
for i in range(5000):
    fact(i)
end_time = time()
print("Time required :", end_time-start_time)

OUTPUT:

Time required : 0.014145374298095703

see the fraction of difference!!

Memoized version is almost 860 times better than naive factorial function.

More Native functions memoized:

1) Fibonacci series:
memory = {}
def fib(n):
    try : return memory[n]
    except:
        if n <= 1 : return n
        else : return fib(n-1)+fib(n-2)