Implement the basic algorithm in Python to deepen your understanding of the algorithm. The Fibonacci sequence is dealt with as the fifth bullet.
A sequence in which the first and second terms are 1, and the sum of the two items before and after the third term. Example) 1,1,2,3,5,8,13,... Implement this in python to deepen your understanding of iterative processing. Below, we show a program that finds the Fibonacci sequence by three methods, but at the end, we also show and consider the code for evaluating them.
The first method is recursion. Recursion is to call yourself (function) again in the defined function. Since the Fibonacci sequence is obtained by repeatedly using the information in the previous section, recursion can be used. The code and the output at that time are shown below.
fibonacci1.py
"""
2020/12/17
@Yuya Shimizu
Fibonacci sequence
Recursion
How to call your function again in a function
"""
def fibonacci(n):
if n==1 or n==2:
return 1
return fibonacci(n-2) + fibonacci(n-1) #Recursion
print(fibonacci(30))
832040
The comment in the above code that indicates recursion is exactly where you are calling yourself (fibonacci function) within yourself (fibonacci function). It should be noted here that recursion requires an end condition of where to end. If you keep calling yourself all the time, it won't end. Therefore, this time, the end condition is that n becomes 1 or 2.
Implementation 2 solves the processing speed problem of Implementation 1. Implementation 1 shown earlier started to slow down a little when it started to exceed 30. The reason is clear: I call my function every time, and I try to find it once (for example, the third term) and use it many times. In implementation 2, a dictionary type array is used to memorize and use the value of the term once obtained. It seems that this memorization is called memoization. The code and the output at that time are shown below.
fibonacci2.py
"""
2020/12/17
@Yuya Shimizu
Fibonacci sequence
Memoization
Record information that is not in the dictionary array
"""
memo = {1:1, 2:1}
def fibonacci(n):
if n in memo:
return memo[n]
memo[n] = fibonacci(n-2) + fibonacci(n-1) #If not registered, calculate and register
return memo[n]
print(fibonacci(100))
354224848179261915075
Even if I asked for 100 items, I was able to calculate quickly. I thought I could go as much as I wanted, and when I tried to ask for 10,000 items, I got the following error message.
[Previous line repeated 1021 more times]
RecursionError: maximum recursion depth exceeded
Apparently recursion has a repeat limit. When I adjusted the number of times as a trial, it seems that the argument 2047 was the limit, and an error message appeared after 2048.
It turns out that there is a limit in implementation 2. A simpler way to find it is to add it to the list in a loop. The code and the output at that time are shown below.
fibonacci3.py
"""
2020/12/17
@Yuya Shimizu
Fibonacci sequence
loop
For simple problems, you can calculate by simply adding them to the list.
"""
def fibonacci(n):
fib = [1, 1]
for i in range(2, n):
fib.append(fib[i-2] + fib[i -1])
return fib[n-1]
print(fibonacci(2048))
45415304437437894250455714462906892027009082612936444289511823902789714525092834356843497180347717304332077420750102996639625006407838018797363807741815915794968069489957662592260489596860563484362187663942834824730009793065752175759244081518806465182648002219755758995565516482064617351513826704211517343602925990599710229276939710372081414109914714493582044185153918055170241694035610145547104337536614028338983073680262684101
2048 items such as an error message in Implementation 2 were also requested safely. I think the processing was very fast as if it was executed.
Actually, how much processing speed can be calculated is measured, compared and evaluated. Since the code structure itself is simple this time, it is not considered in the evaluation. The evaluation code for each code is shown below.
fibonacci1_evaluation.py
"""
2020/12/17
@Yuya Shimizu
Fibonacci sequence
Recursion
How to call your function again in a function
"""
def fibonacci(n):
if n==1 or n==2:
return 1
return fibonacci(n-2) + fibonacci(n-1) #Recursion
#Evaluation
import time
start = time.time()
fibonacci(35)
process_time = time.time() - start
print(process_time)
fibonacci2_evaluation.py
"""
2020/12/17
@Yuya Shimizu
Fibonacci sequence
Memoization
Record information that is not in the dictionary array
"""
memo = {1:1, 2:1}
def fibonacci(n):
if n in memo:
return memo[n]
memo[n] = fibonacci(n-2) + fibonacci(n-1) #If not registered, calculate and register
return memo[n]
#Evaluation
import time
start = time.time()
fibonacci(2047)
process_time = time.time() - start
print(process_time)
fibonacci3_evaluation.py
"""
2020/12/17
@Yuya Shimizu
Fibonacci sequence
loop
For simple problems, you can calculate by simply adding them to the list.
"""
def fibonacci(n):
fib = [1, 1]
for i in range(2, n):
fib.append(fib[i-2] + fib[i -1])
return fib[n-1]
#Evaluation
import time
start = time.time()
fibonacci(2047)
process_time = time.time() - start
print(process_time)
The results of each execution are shown below. However, since it was difficult to match the argument values in calculation, different arguments were given in each program. Code 1 is set to 35 with an argument that is not difficult to calculate, code 2 is set to the limit of 2047, and code 3 is set to 2047 according to code 2. Even with this, I think it can be fully evaluated from the perspective of comparing the three. The output of each is shown below.
6.196547746658325
0.001993894577026367
0.0009958744049072266
The above is the result, but it seems that output 1 has difficulty in processing speed. Output 2 is fast but inferior in that it has its limits. It can be evaluated that the output 3 is superior because it is considerably faster than the others and has no limit.
I've heard of recursion but never used it, and I've never heard of memoization, so it was a good opportunity to learn about them. We also learned that there is a limit to recursion.
Introduction to algorithms starting with Python: Standards and computational complexity learned with traditional algorithms Written by Toshikatsu Masui, Shoeisha
Recommended Posts