メモ化についておさらい

フィボナッチ数列を求めるプログラムを例に、
メモ化についてサクッとメモをしておく。

#!/usr/bin/python


def fib(n):
    u"""
    フィボナッチ数列でn番目に来る要素を返す
    """
    nums = []
    f, s = 0, 1
    while len(nums) <= n:
        nums.append(f)
        f, s = s, f+s
    return nums[n]


def memoFib():
    u"""
    フィボナッチ数列生成のための関数を返す
    """
    memo = [0, 1]
    def fib2(n):
        u"""
        フィボナッチ数列でn番目に来る要素を返す
        """
        if len(memo) > n:
            return memo[n]
        else:
            memo.append(fib2(n-2) + fib2(n-1))
        return memo[n]
    return fib2

if __name__ == '__main__':
    count = 4000

    print "non memo start !!"
    for x in xrange(count):
        fib(x)
    print "non memo end"

    print "memo start !!"
    f = memoFib()
    for x in xrange(count):
        f(x)
    print "memo end"

作成したのはフィボナッチ数列のn番目の要素を返却する関数。

まずfib関数。
こいつは素直にフィボナッチ数列を求める関数。
初期条件(f, s = 0, 1)揃えて、while文の中でfとsをそれぞれ更新していく。
そうしてnums配列にフィボナッチ数列が溜まっていくようにして、
溜まったnums配列のn番目を返してやれば条件を満たす関数の出来上がり。

次に少し複雑なのがmemoFib関数。
こいつはmemoという初期配列を用意して、
fib2という内部で宣言した関数を実行せずに返す。

返ってきたfib2を使ってフィボナッチ数列のn番目の要素を求めるように作った。

fib2も作りは単純な再帰処理で、
再帰の最終点（この場合はlen(memo) > nの状態）での処理を書いて、
それ以外のときは自分を呼び出した結果を用いてmemo配列に要素を追加する。

上記の内容を実行すれば明白な実行速度差が確認できる。
本来ならベンチを取ってどのくらいタイムが縮まっているかを測って書いておこうかと思っていたが、あまりにも一目瞭然で、memoFibを使った方ははっきり言って爆速。

しかし逆に、内部的に再帰処理を持っているため、
何も設定値を変更していなければ、
pythonのデフォルト再帰呼び出しの上限に引っかかりポシャる。
例えばfor文で回さずに、いきなりf(4000)を呼び出すとエラーでコケる。

先ほどメモ化の方は爆速だとのたまったが、
それはこのケースに関しては至極当然の話で、
memoFibの返す関数は過去の実行結果が存在すればその時点で計算が終わる。
つまり「関数が複数回呼ばれる」というケースに対して非常に特化しているといえる。
っつかメモ化って複数回呼ばれるケースに対して特化した最適化手法だと思う。

そもそも上記の例は、詐欺的なやり口でメモ化を押し売るときに使うようなものだ。

なぜならこの例だと、fib関数は最終的なfib(n)を求めるためにfib(n-1)もfib(n-2)も、
一から計算し、しかもせっかく計算した結果は放棄している。
つまりn番目の値を求める前に無駄な計算を山ほど行なっていることになる。
fib関数を作った人間は普通このような使い方はしない。

本来フェアに速度を戦わせるのであれば、下記のようにすべきである。

if __name__ == '__main__':
    count = 200000

    print "non memo start !!"
    fib(count)
    print "non memo end"

    print "memo start !!"
    f = memoFib()
    for x in xrange(count):
        f(x)
    print "memo end"

こうすれば両方共、最終的な結果を得るための計算を一度しか行わない。
上記を実行した結果、両者は同じくらいの速度で結果を返してきた。
そのため今度はベンチマークを取って実行速度を比べてみる。

if __name__ == '__main__':
    import time

    count = 200000

    start = time.time()
    fib(count)
    end = time.time()
    print end - start

    start = time.time()
    f = memoFib()
    for x in xrange(count):
        f(x)
    end = time.time()
    print end - start

上記実行結果がこちらである。

2.32484006882
2.04464197159

何度やっても0.3秒ほどメモ化の方が速い結果となった。　

個人的にはメモ化の方が遅いだろうと思っていた。
それは中で毎回if文を実行しているのと、
for文でxの値をインクリメントする処理が入っているから。

しかし、結果はそれでもメモ化の方が速いと出ている。
が、上述した自分の感覚が間違っているとはどうしても思えない。

ので一旦ここでの結論は下記としておく。
・メモ化が使える場所で使うと、実行速度は上がる
・自分の想定と食い違ったのは下記のような要因があるものと思われる。
・・time.timeを用いたベンチマークの精度が悪い
・・fib関数に無駄が存在する
・・コンパイラがifやインクリメント等の処理を最適化したためほぼノーコストだった

また元気があるときに、
気が向いたら上記の結論を再検証してみる。