Speed Up Slow Functions in Python using Cache

Photo by Jorge Ramirez on Unsplash

What is a Cache?

A cache is a memory used for the storage of frequently used data so that this data can be fetched quickly for subsequent calls. In Python, the library functools gives us the ability to implement a cache. This cache stores the result of previous operations to speed up our function calls.

LRU Cache

The LRU Cache is a type of cache in which the least recently used data is discarded first. This LRU algorithm keeps track of which data was used when. For speeding up the python functions, we will use an LRU cache. The LRU cache can be used with any function and works the best with recursive functions.

Factorial Function

To implement the LRU cache, let’s take the famous factorial function as an example. Below is the factorial function which calculates the factorial of a number.

def factorial(n):
    return n * factorial(n-1) if n else 1

Let’s now define the same function using the LRU cache decorator. The maxsize is the size limit of the LRU cache.

from functools import lru_cache
@lru_cache(maxsize=None)
def factorial_lru_cache(n):
    return n * factorial(n-1) if n else 1

Now, let’s measure the difference between the running times of the two functions. The time is represented in nanoseconds.

# Without LRU Cache
import time
start_time = time.time_ns()
factorial(50)
print(time.time_ns() - start_time)

Without LRU Cache

# With LRU Cache
start_time = time.time_ns()
factorial_lru_cache(50)
print(time.time_ns() - start_time)

With LRU Cache

That is a 1.81x speed increase with a single line of code. Now, let’s try to test the LRU cache on the Fibonacci function.

Fibonacci Function

Fibonacci sequence is a sequence of numbers such that each number is the sum of the two preceding ones, starting from 0 and 1. Below is the Fibonacci function that calculates the nth number in the Fibonacci sequence.

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

Let’s now define the same function using the LRU cache decorator.

@lru_cache(maxsize=None)
def fibonacci_lru_cache(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

Now, let’s measure the difference between the running times of the two functions.

# Without LRU Cache
start_time = time.time_ns()
fibonacci(30)
print(time.time_ns() - start_time)

Without LRU Cache

# With LRU Cache
start_time = time.time_ns()
fibonacci_lru_cache(30)
print(time.time_ns() - start_time)

With LRU Cache

That is a 4214x speed increase with a single line of code. The speed-up is gigantic for so little effort. The LRU cache can come in very handy when you write your next function in Python.

We have completed the speeding up of Python functions using cache. If you like this tutorial, do leave a clap!