Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
5
Help us understand the problem. What is going on with this article?
@chi-na

Python フィボナッチ数列で知る メモ化再帰と動的計画法

More than 1 year has passed since last update.

はじめに

この記事はフィボナッチ数列の計算を通して計算の工夫の重要性を学んだためメモとして投稿します.

フィボナッチ数列とは?

An = An-1 + An-2 (A0 = A1 = 1)の式で表される数列です.

1 1 2 3 5 8 .... と自身の前の2項を足したものが項となる数列です.

実装(再帰, メモ化再帰, 動的計画法)

まず, 再帰で実装

pythonにてフィボナッチ数列の任意の項を求める関数を実装しました.

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(4)を求めるときはfib(3)とfib(2)を求めます.
この場合においてfib(3)は2回計算されます.
このように再帰での実装では無駄な計算が生じてしまいます.

メモ化再帰での実装

メモ化再帰では通常の再帰に加えて, 計算した項の情報を保持します.
今回は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 で 3つの実装についての実行コスト(秒)を計算しました.
結果のグラフを以下に示します.

cal_time.png

Normalが通常の再帰, Memoがメモ化再帰, Dynamic が 動的計画法 です.
グラフより, n = 10 くらいから実行速度について大きな差が出てくることがわかります.

結論

以上より, 簡単な工夫で実行速度が大きく異なることがわかりました.
普段は実行速度についてあまり意識することもなく, 重要性もわかりにくいです.
今回の結果から重い計算においては, データ構造とアルゴリズムの工夫が必須であると感じました.

5
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
5
Help us understand the problem. What is going on with this article?