Since I mentioned the Fibonacci sequence in the Python book I was reading, I will summarize it with a light content like a memo while examining it.
Please note that I am a graduate of design, so there may be various points if you are a graduate of a university related to mathematics or computer science.
It is a sequence named after the Italian mathematician Leonardo Fibonacci (Fibonacci sequence in English).
It is a sequence of values such as 0, 1, 1, 2, 3, 5, 8, 13, 21 ....
The first (index of 0) is 0, the next (index of 1) is 1, and after that, the previous and 2 Written in an expression, it looks like the following (assuming the $ n $ th value in the sequence is $ F_n $).
F_0 = 0\\
F_1 = 1\\
F_n = F_{n - 1} + F_{n - 2}
In addition, this sequence is closely related to the so-called design direction, especially the golden ratio (1: 1.618 ...), and it appears in design-related books.
Even in the natural world, there are various things such as sunflower seeds and nautilus, which are close to the values in this sequence, and it is said that people feel natural and beautiful.
In addition, if you divide a rectangle with a golden ratio into a square and a rectangle, the rectangle will become a rectangle that maintains the golden ratio again, and has various other interesting properties (details are omitted in this article). If you look up articles and books related to mathematics and design, you will find various things, so please check if necessary).
First, without thinking about anything, let's write a process to get the value of the position of the index n of the Fibonacci sequence in Python by calling the function recursively.
def fib(n: int) -> int:
if n == 0:
return 0
if n == 1:
return 1
return fib(n - 1) + fib(n - 2)
As in the above formula, when n is 0 and n is 1, 0 and 1 are returned, respectively, and after that, the total value of the Fibonacci sequence at the positions n-1 and n-2 is set. There is.
Let's run it and see the result.
if __name__ == '__main__':
for n in range(7):
print(f'n = {n}in the case of:', fib(n=n))
n =If 0: 0
n =In case of 1: 1
n =In case of 2: 1
n =In case of 3: 2
n =In case of 4: 3
n =In case of 5: 5
n =In case of 6: 8
You can see that the expected value is taken.
At this rate, if n becomes large, it will take a long time to calculate.
For example, to calculate the value of n = 5, you have to calculate the values of n = 4 and n = 3, and to calculate n = 4, find the values of n = 3 and n = 2. Every time n increases by one, the conditions that need to be calculated increase exponentially like a family tree.
Let's find out how many times the function prepared for trial was executed. I prepared a variable called count as a global variable.
from datetime import datetime
count: int = 0
def fib(n: int) -> int:
global count
count += 1
if n == 0:
return 0
if n == 1:
return 1
return fib(n - 1) + fib(n - 2)
If you try to execute it with n = 34 and n = 35, you can see that the number of function executions has increased significantly just by increasing n by 1.
n=Run sample on 34
if __name__ == '__main__':
print(datetime.now(), 'started')
fib(n=34)
print('Number of times the function was executed:', count)
print(datetime.now(), 'ended')
2020-08-30 15:45:15.097393 started
Number of times the function was executed: 18454929
2020-08-30 15:45:17.980419 ended
n=Run sample on 35
if __name__ == '__main__':
print(datetime.now(), 'started')
fib(n=35)
print('Number of times the function was executed:', count)
print(datetime.now(), 'ended')
2020-08-30 15:49:25.628928 started
Number of times the function was executed: 29860703
2020-08-30 15:49:30.307930 ended
As mentioned above, there are various methods to speed up the calculation when n becomes large, and one of them is to cache the execution result of the function.
For example, if the value of n is the same, the return value will be the same, and when calculating the value of large n, the smaller value can be calculated over and over again, so a specific n is already specified. If the case of the value of is already aggregated, it can be cached and the calculation can be skipped, so that the processing can be completed in a short time even if n increases.
You can cache it using a dictionary, but in Python you can use the built-in module functools and specify the lru_cache decorator.
It's easy to use, just set the lru_cache function as a decorator to the function you want to cache. lru is an abbreviation of Least Recently Used, and it is a method of caching in the form of leaving a new execution result (in this case, leaving the calculation result of n cached toward the end).
This time, since the old cache is not deleted and all are cached, None is specified for the argument maxsize.
from datetime import datetime
from functools import lru_cache
count: int = 0
@lru_cache(maxsize=None)
def fib(n: int) -> int:
global count
count += 1
if n == 0:
return 0
if n == 1:
return 1
return fib(n - 1) + fib(n - 2)
When you execute it, you can see that the process is completed in an instant and the number of times it has passed inside the function has decreased at once.
if __name__ == '__main__':
print(datetime.now(), 'started')
fib(n=35)
print('Number of times the function was executed:', count)
print(datetime.now(), 'ended')
2020-08-30 16:39:49.109241 started
Number of times the function was executed: 36
2020-08-30 16:39:49.110240 ended
Recommended Posts