개시하다

이 글은 피보나치 수열의 계산을 통해 계산 방법의 중요성을 배워 필기 투고로 삼았다.

피보나치 수열과?

An=An-1+An-2(A0=A1 = 1)의 공식으로 표시된 수열.
1 1 2 3 5 8 .... 자신의 앞의 두 항목을 더한 후 항목이 된 수열.

실현(귀속, 비망록귀속, 동적계획법)

우선, 차례로 설치하다

pythn에서 피보나치 수열 임의항의 함수를 구했다.
fib.py

def fib(n):
    if n == 0 or n == 1:
        return 1

    return fib(n-1) + fib(n-2) 

이 함수에 근거하여 임의의 피보나치 수열 항목을 계산할 수 있다.
그러나 이 함수의 계산량은 매우 크다.
fib(5)를 찾기 위해fib(4)와fib(3)가 필요합니다.
fib를 구할 때fib(3)와fib(2)가 필요합니다.
이런 상황에서fib(3)는 두 번 계산된다.
이렇게 귀속되는 실현은 쓸데없는 계산을 만들어 낼 수 있다.

비망록 귀속 실현

비망록은 통상적인 귀환 외에 계산된 항목의 정보를 보류한다.
이번에python의 사전형 구조를 사용합니다.
fib.py

class Fib_memo:
    def __init__(self):
        self.fib_memo = {}

    def cal_fib(self, n):
        if n == 0 or n == 1:
            self.fib_memo[n] = 1
            return 1

        #既に計算した項なら保存した情報を使う
        if n in self.fib_memo.keys():
            return self.fib_memo[n]

        self.fib_memo[n] = self.cal_fib(n-1) + self.cal_fib(n-2)
        return self.fib_memo[n]

계산된 항목을 저장해서 계산의 낭비를 줄일 수 있다.

동적 계획법의 실시

동적 기획 방법에서 비교적 작은 쪽에서 피보나치 수열의 항목을 계산한다
계산의 낭비를 줄였다.
fib.py

def fib_dynamic(n):
    # 結果を保持する辞書
    cal_result = {}

    # 初期値の設定
    cal_result[0] = 1
    cal_result[1] = 1

    if n == 0 or n == 1:
        return 1

    for i in range(2, n+1):
        cal_result[i] = cal_result[i-1] + cal_result[i-2]

    return cal_result[n]

확인

n=1~15는 세 가지 실현된 집행 원가(초)를 계산했다.
결과의 도표는 다음과 같다.

정규는 통상적인 귀환이고 메모는 필기화 귀환이며 다이나믹은 동적 계획법이다.
도표에서 알 수 있듯이 n=10 정도의 집행 속도는 매우 큰 차이가 있을 것이다.

결론

위에서 말한 바와 같이 간단한 방법을 통해 우리는 실행 속도가 매우 다르다는 것을 발견하였다.
평소 실행 속도에 대한 의식이 많지 않아 그 중요성을 이해하기도 어렵다.
이번 결과에서 나는 중계산에서 데이터 구조와 알고리즘에 공을 들이는 것이 필요하다고 생각한다.