再帰関数のメモ化(Memoization for Recursive Functions)とY Combinatorの速度計測

解説は前記事再帰関数のメモ化(Memoization for Recursive Functions)とY Combinator - 技術memo

以下、F# Interactiveに流し込むだけ。

// memoize by mutable Dictionary
let memoize f =
    let cache = new System.Collections.Generic.Dictionary<_,_>() in
    (fun x-> cache.TryGetValue(x) |> function
        | true,r -> r
        | _ -> let r = f x in cache.Add(x,r); r)

// memoize by FSharpMap
let memoize_map f =
    let cache = ref Map.empty<_,_> in
    (fun x-> (!cache).TryFind(x) |> function
        | Some r -> r
        | _ -> let r = f x in cache := (!cache).Add(x,r); r)

// Fibonacci
let rec fib_normal x = if x <= 2 then 1 else fib_normal (x-1) + fib_normal (x-2)

// Fibonacci(Y Combinator version)
let rec fix f x = f (fix f) x
let fib_maker f x = if x <= 2 then 1 else f (x-1) + f (x-2)
let fib_fix = fix fib_maker

// Memoized Fibonacci
let fib_memo =
    let rec f x =
        if x <= 2 then 1 else f_memo (x-1) + f_memo(x-2)
    and f_memo = memoize f in
    f_memo

// Memoized Fibonacci(Y Combinator version)
let fix_memo f =
    let rec fix x = f m_fix x
    and m_fix = memoize fix in
    m_fix
let fib_fix_memo = fix_memo fib_maker

// Memoized Fibonacci(Y Combinator version) by FSharpMap
let fix_memo_map f =
    let rec fix x = f m_fix x
    and m_fix = memoize_map fix in
    m_fix
let fib_fix_memo_map = fix_memo_map fib_maker

// benchmark
open System.Diagnostics
let benchmark n f =
    let sw  = new Stopwatch()
    sw.Start()
    for i in 1..n do f() |> ignore
    sw.Stop()
    sw.Elapsed

// test
let n = 15
let repeat = 500000
let bench_fib f = benchmark repeat (fun ()->f n) |> printfn "%A"
do printfn "*** benchmark fib_normal * %d ****" repeat
do bench_fib fib_normal
do printfn "*** benchmark fib_fix * %d ****" repeat
do bench_fib fib_fix
do printfn "*** benchmark fib_memo * %d ****" repeat
do bench_fib fib_memo
do printfn "*** benchmark fib_fix_memo * %d ****" repeat
do bench_fib fib_fix_memo
do printfn "*** benchmark fib_fix_memo_map * %d ****" repeat
do bench_fib fib_fix_memo_map

(* result...
*** benchmark fib_normal * 500000 ****
00:00:00.9523121
*** benchmark fib_fix * 500000 ****
00:00:29.8254891
*** benchmark fib_memo * 500000 ****
00:00:00.0205440
*** benchmark fib_fix_memo * 500000 ****
00:00:00.0200061
*** benchmark fib_fix_memo_map * 500000 ****
00:00:00.0347660

in F# Interactive(version 11.0.60610.1) and my PC
*)

fib_fixがfib_normalより30倍くらい遅いですね。これが関数呼び出しのオーバーヘッド……なのでしょうか？

メモ化してしまえば繰り返し分の違いしか出ないので、fib_memo, fib_fix_memoは大差無しと見ていいでしょう。

FSharpMap版も作ってみましたが、Dictionary版とさほど変わらず。こういったリピート回数で時間を増やすテストだと、要素の追加より検索の方がよほど回数が増えるので、データ構造のMutable/Immutableの違いはそれほど出ないということでしょうか。