1000 Python Questions

Get 1 Python question daily. Join this telegram channel https://t.me/python1000questions

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.

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/

Related Articles:

Difference between tuples and lists, raw_input and input, shallow and deep copy, args and kwargs and other different terms explained in python...

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...

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++...

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...

0 thoughts on 'Improving Python Code Performance By Using Lru_Cache Decorator'

Leave a comment:

Please subscribe to get the latest articles in your mailbox.

Recent Posts:

Please subscribe to get the latest articles in your mailbox.