Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

memoization
python
achieve

How to achieve memoization in Python

Educative Answers Team

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.

svg viewer

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
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring