フィボナッチ数計算を動的計画法/メモ化再帰でやる

すぐ忘れるのでいい練習題材だなって。
この記事下部に張った参考リンクのwikipediaさんによると、動的計画法ってのは多義的なもんらしい。
使い分けとしては

てなもんだと考えておこう。クオンツ的にはメモ化再帰の方が大事ですな。

以下、F#での実装例。実行時間計測したかったんだけど、ディレクティブ忘れてしもうた。

//ふつー?に再帰でフィボナッチ
let rec fib x = 
    match x with
    | 0|1 -> x
    | _ -> fib (x-1) + fib (x-2)
//動的計画法版
let fib_dp x = 
    let memo = Array.zeroCreate (x+1)
    memo.[0] <- 0
    memo.[1] <- 1
    for i in 2..x do
        memo.[i] <- memo.[i-1] + memo.[i-2]
    memo.[x]
//メモ化再帰版
let fib_mr x = 
    let memo = Array.zeroCreate (x+1)
    memo.[0] <- 0
    memo.[1] <- 1
    let rec fib_mr_inner x = 
        match x with
        | 0|1 -> x
        | _ ->
            if memo.[x] = 0 then
                memo.[x] <- fib_mr_inner (x-1) + fib_mr_inner (x-2)
            memo.[x]
    fib_mr_inner x

#time "on"だったようだ。計測してみる。

> #time "on";;

--> Timing now on

> printfn "Fibonacci number 1: %d" (fib 45);;
Fibonacci number 1: 1134903170
Real: 00:00:10.051, CPU: 00:00:10.062, GC gen0: 0, gen1: 0, gen2: 0
val it : unit = ()
> printfn "Fibonacci number 1: %d" (fib_dp 45);;
Fibonacci number 1: 1134903170
Real: 00:00:00.002, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it : unit = ()
> printfn "Fibonacci number 1: %d" (fib_mr 45);;
Fibonacci number 1: 1134903170
Real: 00:00:00.002, CPU: 00:00:00.015, GC gen0: 0, gen1: 0, gen2: 0
val it : unit = ()

明らかに通常の再帰は遅い。もうちょい動的計画法とメモ化再帰を増やしてみる。

> for i in 1..100000 do fib_dp 10000 |> ignore;;
Real: 00:00:03.467, CPU: 00:00:03.447, GC gen0: 2500, gen1: 1, gen2: 0
val it : unit = ()
> for i in 1..100000 do fib_mr 10000 |> ignore;;
Real: 00:00:16.637, CPU: 00:00:16.614, GC gen0: 2500, gen1: 2, gen2: 0
val it : unit = ()

動的計画法の方が速いなぁ。

参考