Skip to content

Latest commit

 

History

History
254 lines (191 loc) · 6.83 KB

7.md

File metadata and controls

254 lines (191 loc) · 6.83 KB
Raw

再帰ドリル(7)：メモ化

フィボナッチ数列を素朴な再帰で実装したコードを思い出そう。

my_fib :: Integer -> Integer
my_fib 0 = 0
my_fib 1 = 1
my_fib n = my_fib (n - 2) + my_fib (n - 1)

このコードは美しいが、実際に動かしてみると耐えられないくらい遅いことが分かる。

> :set +s
> my_fib 33
3524578
(12.38 secs, 1100894476 bytes)

遅い理由は、下の図のように同じ計算を何度も繰り返すからだ。

フィボナッチ数列の樹状計算

これまで学んだように、フィボナッチ数列は簡単に末尾再帰の形に変更できる。

my_fib_iter :: Integer -> Integer
my_fib_iter a = iter a 0 1
  where
    iter :: Integer -> Integer -> Integer -> Integer
    iter 0 x _ = x
    iter n x y = iter (n - 1) y (x + y)

そのコードは無駄な再計算をしないので速い。

> my_fib_iter 33
3524578
(0.00 secs, 512436 bytes)

残念ながら、あらゆる再帰が末尾再帰に簡単に直せる訳ではないし、簡単に高速化できる訳でもない。

再帰の形を変えずに高速化する常套手段はメモ化である。メモ化とは、計算した結果を辞書に登録してキャッシュし、再計算を防ぐことである。動的計画法と呼ばれることもある。

Haskellでのメモ化

ここからは Haskell 固有の話なので、興味がない方は読まなくても構わない。

Haskell では、純粋な実装を目指したくなる。そのためには、辞書を引数として持ち回せばいい。

import Data.Map (Map)
import qualified Data.Map as M

type Table = Map Integer Integer

my_fib_table :: Integer -> Integer
my_fib_table n = fst (my_fib_tbl n M.empty)

my_fib_tbl :: Integer -> Table -> (Integer,Table)
my_fib_tbl 0 tbl = (0,tbl)
my_fib_tbl 1 tbl = (1,tbl)
my_fib_tbl n tbl = case M.lookup n tbl of
    Nothing -> (xn,tbln)
    Just x  -> (x,tbl)
  where
    (x1,tbl1) = my_fib_tbl (n - 2) tbl
    (x2,tbl2) = my_fib_tbl (n - 1) tbl1
    xn = x1 + x2
    tbln = M.insert n xn tbl2

育てた辞書を引き継いで行く必要があるので、答えと組にして辞書を返す必要がある。このため、美しさに欠けることは否めない。

実際に動かして、メモ化の効果を見てみよう。

> my_fib_table 33
3524578
(0.00 secs, 548312 bytes)

他の言語と同様に副作用を用いてメモ化を実装すると、以下のようなコードになる。

import Data.IORef
import Data.Map (Map)
import qualified Data.Map as M

my_fib_io :: Integer -> IO Integer
my_fib_io a = do
    ref <- newIORef $ M.fromList [(0,0),(1,1)]
    fib a ref
  where
    fib :: Integer -> IORef (Map Integer Integer) -> IO Integer
    fib n ref = do
        memo <- readIORef ref
        case M.lookup n memo of
            Just z  -> return z
            Nothing -> do
                x <- fib (n - 2) ref
                y <- fib (n - 1) ref
                let z = x + y
                modifyIORef ref (M.insert n z)
                return z

こちらもメモ化の効果を見てみよう。

> my_fib_io 33
3524578
(0.00 secs, 0 bytes)

memoFib の返り値が IO Integer であるのは、Haskeller としてはくやしい。そこで、禁断の unsafePerformIO を使いたくなる。

import Data.IORef
import Data.Map (Map)
import qualified Data.Map as M
import System.IO.Unsafe

my_fib_unsafe :: Integer -> Integer
my_fib_unsafe a = unsafePerformIO $ do
    ref <- newIORef $ M.fromList [(0,0),(1,1)]
    fib a ref
  where
    fib :: Integer -> IORef (Map Integer Integer) -> IO Integer
    fib n ref = do
        memo <- readIORef ref
        case M.lookup n memo of
            Just z  -> return z
            Nothing -> do
                x <- fib (n - 2) ref
                y <- fib (n - 1) ref
                let z = x + y
                modifyIORef ref (M.insert n z)
                return z

ただ、unsafePerformIO を使うと後ろ髪を引かれる思いになることは確かだろう。

memoize パッケージの memoize

幸いにも、純粋にメモ化する方法が知られている。深い説明はこのドリルの範囲を超えるので、今回は単に memoize パッケージで定義されている memoize 関数を使おう。

まず、memoize パッケージをインストールしていただきたい。

% cabal install memoize

memoize を使うには、以下のようにする。

  1. 再帰関数fooが呼び出す関数を foo から foo_memo に変える。
  2. foo_memo = memoize foo と定義する。(メモ化する関数(memoizeなど)は、foo の引数の数によって適切な関数を選ぶこと。)

fib のコードには、以下のようにメモ化の実装に変更できる。

import Data.Function.Memoize

my_fib_memo :: Integer -> Integer
my_fib_memo = memoize my_fib

my_fib :: Integer -> Integer
my_fib 0 = 0
my_fib 1 = 1
my_fib n = my_fib_memo (n - 2) + my_fib_memo (n - 1)

実際に動かしてメモ化の効果を確かめてみよう。

> my_fib_memo 33
3524578
(0.00 secs, 518892 bytes)

演習：カタラン数

以下が経路の総数を計算するコードであった。

my_catalan :: Integer -> Integer
my_catalan x = my_cat x x

my_cat :: Integer -> Integer -> Integer
my_cat _ 0 = 1
my_cat m n
  | m == n    = my_cat m (n - 1)
  | otherwise = my_cat m (n - 1) + my_cat (m - 1) n

これをメモ化を使って高速にせよ。

my_catalan_memo :: Integer -> Integer
my_catalan_memo n = my_cat_memo n n

my_cat_memo :: Integer -> Integer -> Integer
my_cat_memo = undefined

my_cat :: Integer -> Integer -> Integer
my_cat = undefined

以下が二分木の総数を計算するコードであった。

my_catalan2 :: Integer -> Integer
my_catalan2 0 = 1
my_catalan2 n = sum (zipWith (*) xs ys)
  where
    xs = map my_catalan2 [0 .. n - 1]
    ys = map my_catalan2 [n - 1, n - 2 .. 0]

これをメモ化を使って高速にせよ。

my_catalan2_memo :: Integer -> Integer
my_catalan2_memo = undefined

my_catalan2 :: Integer -> Integer
my_catalan2 = undefined

演習：コインの両替

以下がコインの両替を解くコードであった。

my_coin :: Integer -> [Integer] -> Integer
my_coin 0 _   = 1
my_coin _ []  = 0
my_coin n (c:cs)
  | n < 0     = 0
  | otherwise = my_coin n cs + my_coin (n - c) (c:cs)

これをメモ化を使って高速にせよ。

my_coin_memo :: Integer -> [Integer] -> Integer
my_coin_memo = undefined

my_coin :: Integer -> [Integer] -> Integer
my_coin = undefined

[目次] [演習7]