Python Advanced: How to Utilize Memoization Technique in Python

Memoization Technique

A programming approach called recursion involves a function continuously calling itself until a termination condition is satisfied. Calculating the Fibonacci series and calculating factorial are two examples of applications where recursion is used. However, the difficulty with them is that there is a possibility in the recursion tree that the sub-problem that has already been solved is being solved again, which increases overhead.

Donald Michie first used the term “memoization” in 1968. Its root is the Latin word memorandum, which means “to be recalled.” Despite having some similarities to the word “memory,” it is not a typo of that word. Programs can be made faster in computers by using a method called memorization. This is achieved by memorizing the computation outcomes of input that have been processed, such as the outcomes of function calls. The results from earlier calculations can be reused if the same input or a  function call with the same parameters is utilized, preventing the need for more calculations.

Memorization is a method for saving intermediate findings so that they can be utilized to speed up programs and prevent repeating calculations. It can be applied to improve recursive programs. Memorization is possible in Python with the use of function decorators.

Example:

def factorial(arg):
   if arg == 1:
       return 1
   else:
       return arg * factorial(arg-1)
      
 
print(factorial(10))
print(factorial(10))
print(factorial(10))
print(factorial(10))

Output:

3628800
3628800
3628800
3628800

Memoization using decorator

We also provided a method for enhancing the recursive version’s runtime behavior by using a dictionary to memorize the function’s earlier calculated values. Although we didn’t call it that, this is an example of explicitly applying the memoization technique. The drawback of this approach is that the original, elegant recursive implementation’s clarity and beauty are lost.

We modified the code for the recursive Factorial function, which is the “issue.” Our factorial function is left unchanged by the following code, preserving its readability and clarity. For this reason, we create and employ a function called memoization_mathod. This function is accepted as an argument.

Example:

 
memory = {}
def memoization_method(f):
  
  
   def exec(num):
       if num not in memory:
           memory[num] = f(num)
           print( memory[num], ' Item saved in memory')
       else:
           print('Returning item from saved memory')
       return memory[num]
 
   return exec
  
@memoization_method
def factorial(arg):
   if arg == 1:
       return 1
   else:
       return arg * factorial(arg-1)
 
print(factorial(10))
print(factorial(10))
print(factorial(10))
print(factorial(10))

Output:

 
1  Item saved in memory
2  Item saved in memory
6  Item saved in memory
24  Item saved in memory
120  Item saved in memory
720  Item saved in memory
5040  Item saved in memory
40320  Item saved in memory
362880  Item saved in memory
3628800  Item saved in memory
3628800
Returning item from saved memory
3628800
Returning item from saved memory
3628800
Returning item from saved memory
3628800

1. The “memoization_method” is a function that has been defined. Its major function is to keep the interim findings in the memory variable.
2. The function to compute the factorial is the second function with the name factorial. The function memoization method, a decorator, has annotated it. Because of the idea of closures, the factorial has access to the memory variable. An annotation functions similarly to writing.
3. Recursive procedures as well as the storage of interim results happen when factorial(10) is called. Every time a computation is required, it is determined whether the answer is already stored in memory. If the answer is affirmative, the value is used; if not, it is calculated and kept in memory.
4. The output of this program allows us to confirm that memoization is effective.

factorial = memoization_method(factorial)

Memoization is a technique used in computer science to speed up function calls by caching the results of previous function calls. In Python, this can be achieved through the use of dictionaries and decorators.

The importance of memoization lies in its ability to reduce the time complexity of function calls by avoiding the need to recalculate the same result multiple times. This can be particularly useful when working with large datasets or complex computations.