再帰関数のメモ化(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の違いはそれほど出ないということでしょうか。