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.
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:
1. https://docs.python.org/3/library/functools.html#functools.lru_cache
2. https://realpython.com/python-traceback/
2. https://realpython.com/python-traceback/
0 comments on 'Improving Python Code Performance By Using Lru_Cache Decorator'
Related Articles:
Zen of python, import this, the hidden easter egg with the joke, source code of Zen of python disobey itself...
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, 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++...
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...
Recent Posts:
