動的計画法の基本実装してみたった

とりあえず最初ということで簡単なところからいきます。本日生命情報学という授業でちろっと出てきてまだちゃんと実装したことなかったのでpythonで動的計画法をやってみようと思いました。

動的計画法とは？

処理が大きい問題を分解してそこだけ解いて速く解こう！っていうアルゴリズムらしいです。今回はフィボナッチ数列を使って[1]のサイトに書かれているトップダウン型とボトムアップ型の求め方をやってみて、最後に計算時間を計ろうと思います。

参考にしたサイトはここ

まずは普通のフィボナッチ数列

def nomal_fib(n: int):
    #初項 = 第0項目とする
    if n < 2:
        return 1
    else:
        return nomal_fib(n-1)+nomal_fib(n-2)

これは実装簡単ですね。漸化式になっていて、 $F(x)=F(x-1)+F(x-2)$ となっていて $F(1)=F(2)=1$ です。ちなみに計算回数は $2^n$ となっていて、膨大です。

ではトップダウン型をやっていきましょう。

class topDown_fib:
    def __init__(self):
        self.node = [1, 1]
    def __call__(self, n: int):
        if n < len(self.node):
            return self.node[n]
        else:
            A = self.__call__(n-1) + self.__call__(n-2)
            self.node.append(A)
            return self.node[-1]

これも基本的な計算は同じですが、self.nodeに計算した値を入れ同じ数字はわざわざ計算をしなくても良いようになっています。(これをメモ化と言うらしいです)

次にボトムアップ型を試してみようと思います。

def bottomUp_fib(n: int):
    if n==0:
        return 1
    else:
        a = b = A = 1
        for i in range(n-1):
            A = a+b
            a = b
            b = A
        return A

こちらは比較的元ブログのようなプログラムになってしましました...ゴールとスタートが見えてるなら最初っから最後まで計算しちゃえば良いじゃない！って感じです。(分割統治法と言うらしいですね...)

では最後にお待ちかねの計測ったーいむ！

f:id:takanori_AB:20181115205453p:plain

第20項まで求めてtime.perf_counter()で計りました。これは予想していない程に格段に違いましたね。これがアルゴリズムの力なのでしょうかね。

今回の感想

今回トップダウン型が2番手に来ましたが、なんとなくまだ伸びしろがありそうですね。。。次回こそは本業(趣味)である深層学習について書きたいです(^^♪ではまた次回～