フィボナッチ数計算を動的計画法/メモ化再帰でやる
すぐ忘れるのでいい練習題材だなって。
この記事下部に張った参考リンクの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 = ()
動的計画法の方が速いなぁ。
参考