Related Tags

memoization
python
achieve

# How to achieve memoization in Python

In Python, memoization optimizes the function by caching its output for future use. Once the function is memoized, it will be calculated for the first time; f​or every other time, it will be retrieved from the cache.

Memoization is a great technique for computationally expensive codes.

## Code

Consider this computationally expensive code:

# Fibonacci Numbers
def fib(num):
if num == 0:
return 0
elif num == 1:
return 1
return fib(num - 1) + fib(n - 2)


## Memoization can be implemented using

• Decorater in Python
• functiontools.lru_cache

## Decorater in Python

In the code snippet below, a cache is used to store the data. If the required data is already computed, it returns its output. Otherwise, it calls the required function:

def memoize_fib(func):
cache = {}
def inner(arg):
if arg not in cache:
cache[arg] = func(arg)
return cache[arg]
return inner


functiontools.lru_cache: a built-in decorater in Python.

## Implementation

We have given three codes for comparing the execution times for each case (i.e., Simple, lru_cache, Decorator).

The timeit() function calculates the execution time for our code. For more information, click ​here.

import functools
import timeit

@functools.lru_cache(maxsize=150)
def fib(num):
if num == 0:
return 0
elif num == 1:
return 1
return fib(num - 1) + fib(num - 2)

print(timeit.timeit('fib(30)', globals=globals(), number=1))
print(timeit.timeit('fib(30)', globals=globals(), number=1))
print(timeit.timeit('fib(30)', globals=globals(), number=1))

RELATED TAGS

memoization
python
achieve
RELATED COURSES

View all Courses

Keep Exploring

Learn in-demand tech skills in half the time