メモ化のまとめとして処理速度について少し検討し、メモの探索をもう少し効率の良いものに実装しなおしたい。

特に理由もなく、なんとなく fib n の定義における fib (n-1) と fib (n-2) の加算順序を逆にしてみたところ、極端に速度が低下したので気になって少し調べてみた。

Fibonacci再考

メモ化された Fibonacci 関数の動きを考えてみる。例えば、fib 5 を計算した場合の再帰呼び出しの構造は以下のようになっている:

fib 5 = fib 4 = fib 3 = fib 2 = fib 1 = 1
          |       |       |       +
          |       |       +     fib 0 = 0
          |       +       |
          |       |     fib 1 = 1
          +       |
          |     fib 2 = fib 1
          |               +
          |             fib 0
          |
        fib 3 = fib 2 = fib 1
                  |       +
                  +     fib 0
                  |
                fib 1

fib 5 = fib 4 + fib 3 の計算でまず fib 4 を求めようとする。メモされていないので fib 3 + fib 2 の計算をする。fib 3 もメモされていないので・・・と、以降、fib 2, fib 1 と順に再帰呼び出しを続ける。fib 1 = 1, fib 0 = 0 に達した時点で再帰が終わり、今度は fib 1, fib 2 と戻ってくるのだが、戻ってくるときに必要な値は全て計算済みなので、メモ化された値を取り出すだけで終わる。つまり、上の図で言うと一番上の行の横一列だけで計算が終わり、残りは全てメモの値となっているのである。しかも、メモの実装にリストを使い、計算した値を順次リストの頭部に置いているので、fib 4 まで計算したときのメモの中身は [fib 4, fib 3, fib 2, fib 1, fib 0] となっており、ここで fib 3 を探しに行くと先頭から2番目にあるのですぐに見つかる。探索に失敗するのは一番最初だけであるが、このときはメモされた値が無いので走査に時間がかからない。

次に、fib n の定義を fib (n-2) + fib (n-1) に変更し、同様の図を書いてみる。

fib 5 = fib 3 = fib 1 = 1
          |       +
          |     fib 2 = fib 0 = 0
          |               +
          |             fib 1 = 1
          |
        fib 4 = fib 2 = fib 0
                  |       +
                  +     fib 1
                  |
                fib 3 = fib 1
                          +
                        fib 2 = fib 0
                                  +
                                fib 1

今度もまず一番上の行を右側へ計算していくが、fib 1 をメモしたあと fib 2 の 探索に失敗して fib 0 + fib 1 の計算をする。fib 3 の結果をメモしたあと fib 4 探索に失敗して fib 2 + fib 3 の計算をする。探索に失敗するということはリスト全体を走査していることになるので非常に時間がかかる。実際、n=30000 くらいの値で処理時間を比べてみると、当初のコードでは1秒もかからないのに対し、加算順序を変えたコードでは6秒近くも要しているのである。

両替問題

山下さんの記事には、メモ化をしたコードの場合「１万円札の両替もすぐに結果が出る」と書かれているのだが、前記事で書いたコードではなかなか終わらない。５千円の両替でも3秒ほどかかった。山下さんのコードでもメモの実装にはリストを使っているのだが、計算した順に並べていくのではなく、キーの降順でソートしてあるため探索が速いようだ。

Mapを使う

以上で明らかなように、何の工夫もないリストでメモを実装すると線型探索になってしまい、メモされていない値の検索のたびにリスト全体を走査することになるのでとても効率が悪い。ソートして二分探索を行うなどの工夫をしても良いが、せっかく便利なものがライブラリにあるのでそれを利用することにする。

メモの実装にとても都合が良いのは Data.Map である。キーに対応する値の検索（この場合、n から fib n の検索）を高速に行える。GHCのライブラリマニュアルで Data.Map.Lazy を見ると、lookup の型の下に O(log n) と書かれている¹。Haskell のライブラリドキュメントにはこのように関数の処理時間のオーダーが書かれていることが珍しくない。マップの lookup の場合、マップのサイズ n の対数時間で探索ができる、ということが分かる。工夫なしリストの場合は O(n) であるから、メモ探索の効率がかなり改善されることが期待できる。

メモ処理部分の実装を変更してみる。Map版への書き換えは容易で、以下のようになる:

import qualified Data.Map as M      -- Mapライブラリを取り込む

type Memo a b = M.Map a b           -- Memo の型を Map に変更

getResult :: Ord a => a -> Memo a b -> Maybe b
getResult = M.lookup                -- Map の lookup に変更

putResult :: Ord a => (a, b) -> Memo a b -> Memo a b
putResult = uncurry M.insert        -- insert をuncurry化して、(a, b) の型を
                                    -- 扱えるようにする。

sEmpty :: Memo a b
sEmpty = M.empty                    -- 空のMap

このように改造すると、fib n = fib (n-2) + fib (n-1) と書き換えても遅くならず、また、１万円の両替の場合も即座に答えが出るようになった。

*Main> runMemo mcc (10000, [500,100,50,10,5,1])
7844606371
(0.17 secs, 69293096 bytes)

汎用的に使えるメモとしてはこれでほぼ満足できるものになったと思うので、メモ化の話はここで一区切りとする。

次回からはモナドのことについて、のんびりペースで書いていこうと思う。