How to use Caching in Python

While writing code, sometimes we need to store the result of the computation to avoid re-calculating it again which is also called Caching. In python, there is a systematic way to tackle this program flow.

Lets take an example of Fibonacci number. Fibonacci numbers are defined as following

So to calculate nth fiboncaai number we need to calculate n-1th and n-2th fiboncacci number with the base case for n=0 and n=1

For example, if we want to calculate F[3], i,e, 3rd fibonacci number

F[3] = F[2] + F[1]
     = (F[1] + F[0]) + 1
     = (1 + 0) + 1
     = 2

To calculate 5th fibonacci number

F[5] = F[4] + F[3]

F[4] = F[3] + F[2]
     = (F[2] + F[1]) + (F[1] + F[0])
     = ((F[1] + F[0]) + 1) + (1 + 0)  
     = ((1 + 0) + 1) + 1
     = (1 + 1) + 1
     = 2 + 1
     = 3

F[3] = F[2] + F[1]
     = (F[1] + F[0]) + 1
     = (1 + 0) + 1
     = 1 + 1
     = 2

So,

F[5] = F[4] + F[3]
     = 3 + 2
     = 5

That is how it can be implemented in python,

def fibonacci(n):
    if n <= 1: return n  # base case

    return fibonacci(n - 1) + fibonacci(n - 2)

One thing we notice that there are some duplicate calculations that can be avoided. For example, in the calculation of F[4] we already have calculated F[2], so later on, wherever we need F[2], i.e. while calculating F[3], we should have some mechanism to retrieve it. This is where caching comes in.

Python provide Least Recenty Used cache or LRU cache through its functools module. We need to do only one line change to make it cache values,

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci(n):
    if n <= 1: return n  # base case

    return fibonacci(n - 1) + fibonacci(n - 2)

We have set maxsize = None to make it store as many number as it want. However you can set maximum number of distinct “n” you want to store result for.

Now, whenever the Fibonacci function is called for n = 2, python checks if there is a result stored for input argument n=2, if yes then return the result else calculate it.

Share this...
Share on Facebook
Facebook

1 thought on “How to use Caching in Python”

Leave a Comment

error: Content is protected !!