Blog available for sell
This blog is available for sale. Please 'contact us' if interested.
Advertise with us
performance python-tips   0   12529
Improving python code performance by using lru_cache decorator


Here is the program to generate the Fibonacci series up to the number provided as a command-line argument.

import sys


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


number = int(sys.argv[1])
print([fibonacci(x) for x in range(number)])


Output, when this code is executed for input number 10, is as below:

rana@brahma:others$ python3 fibonacci.py 10
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Simple. Right.

I tried to execute the same function for input 100 but it took so much time that I have to cancel the execution.

rana@brahma:others$ python3 fibonacci.py 100
^CTraceback (most recent call last):
  File "fibonacci.py", line 12, in <module>
    print([fibonacci(x) for x in range(number)])
  File "fibonacci.py", line 12, in <listcomp>
    print([fibonacci(x) for x in range(number)])
  File "fibonacci.py", line 8, in fibonacci
    return fibonacci(n - 2) + fibonacci(n - 1)
  File "fibonacci.py", line 8, in fibonacci
    return fibonacci(n - 2) + fibonacci(n - 1)
  .... output removed intentionally ......
    return fibonacci(n - 2) + fibonacci(n - 1)
  File "fibonacci.py", line 8, in fibonacci
    return fibonacci(n - 2) + fibonacci(n - 1)
  File "fibonacci.py", line 8, in fibonacci
    return fibonacci(n - 2) + fibonacci(n - 1)
  File "fibonacci.py", line 8, in fibonacci
    return fibonacci(n - 2) + fibonacci(n - 1)
  File "fibonacci.py", line 8, in fibonacci
    return fibonacci(n - 2) + fibonacci(n - 1)
KeyboardInterrupt
rana@brahma:others$ 

What is this long trail of calls? We will get back to this in some time.

I tried again for a lower number, 35. It took some time and I tried to measure it.

rana@brahma:others$ time python3 fibonacci.py 35
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887]

real	0m4.098s
user	0m4.090s
sys	0m0.008s
rana@brahma:others$ 

It took sweet 4 seconds to get the result. 

Why this simple program to calculate the Fibonacci sequence of 35 terms is getting so long? To understand this let's have a look at the below diagram which I borrowed from here.

fibonacci series pythoncircle



The above diagram is showing the number of calls to the same function with different arguments when calculating the 6th Fibonacci number. 
The function is called with an argument 0, 5 times.
The function is called with argument 1, 8 times.
The function is called with argument 2, 5 times.
The function is called with argument 3, 3 times.
The function is called with argument 4, 2 times.
The function is called with argument 5, 1 time.
The function is called with argument 6, 1 time.

Hence the same function is called 25 times. This is what is taking time in returning the result.


Can we improve the performance of this code?

As we can see, there are multiple repeated calls with the same argument. What if we can cache the results and when there is a call to the function with the same argument, return the computed value instead of re-calculating it.

Presenting to you the lru_cache decorator from functools.

import sys
from functools import lru_cache


@lru_cache()
def fibonacci(n):
if n < 2:
return n
else:
return fibonacci(n - 2) + fibonacci(n - 1)


number = int(sys.argv[1])
print([fibonacci(x) for x in range(number)])

Output:

rana@brahma:others$ time python3 fibonacci.py 35
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887]

real	0m0.035s
user	0m0.026s
sys	0m0.009s
rana@brahma:others$

Only 35 milliseconds. More than 100 times faster response. So what happened here?

lru_cache decorator wraps the function with memoization callable which saves the most recent calls. So basically it stores the already computed values and reuses them whenever required.
To prevent the growth of LRU cache without bounds, it is recommended to specify the maxsize in lru_cache decorator. If specified, it will store only maxsize recent calls.

To check the effectiveness of LRU cache, we can call cache_info function on wrapped function.

import sys
from functools import lru_cache


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


number = int(sys.argv[1])
print([fibonacci(x) for x in range(number)]) # cache effectiveness
print(fibonacci.cache_info())

rana@brahma:others$ time python3 fibonacci.py 35
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887]
CacheInfo(hits=66, misses=35, maxsize=64, currsize=35)

real	0m0.034s
user	0m0.034s
sys	0m0.000s
rana@brahma:others$ 

You can measure the more accurate timings using timeit python module.


Now coming back to the long trail of calls we saw above when we canceled the execution of program midway. This is the traceback generated by python when an exception is thrown. Traceback is also known as stack trace or traceback. It provides the list of function calls being made at that point of time in code when the exception occurred. 
What exception was thrown in the above case? As you can see in the last line of code it is a KeyboardInterrupt exception. Read more about it in the references section below.
 

References:

performance python-tips   0   12529
0 comments on 'Improving Python Code Performance By Using Lru_Cache Decorator'
Login to comment


Related Articles:
Python easter egg - import this and the joke
Zen of python, import this, the hidden easter egg with the joke, source code of Zen of python disobey itself...
Solving Python Error- KeyError: 'key_name'
Solving KeyError in python, How to handle KeyError in python dictionary, Safely accessing and deleting keys from python dictionary, try except Key error in Python...
Print statement in Python vs other programming languages
print statement in Python vs Other programming languages, comparing python simplicity with other programming languages, how to print a string in python, print statement in python, comparing python with other languages, python vs java, python vs c++...
5 common mistakes made by beginner python programmers
Most common mistakes made by beginner python programmers, Things to avoid by python programmers, Most common pitfalls/ gotchas in python, Bitten by python scenarios, tips for beginner python programmers, python beginner programmers should avoud these mistakes...
DigitalOcean Referral Badge

© 2024-2025 Python Circle   Contact   Sponsor   Archive   Sitemap