F#
メモ化

簡単なメモ

Memoizationは、同じ結果を複数回計算するのを避けるために、関数の結果をキャッシュすることで構成されています。これは、コストのかかる計算を実行する関数を扱う場合に便利です。

例として単純階乗関数を使うことができます：

let factorial index =
    let rec innerLoop i acc =
        match i with
        | 0 | 1 -> acc
        | _ -> innerLoop (i - 1) (acc * i)

    innerLoop index 1

この関数を同じパラメータで複数回呼び出すと、同じ計算が何度も繰り返されます。

Memoizationは階乗結果をキャッシュし、同じパラメータが再び渡された場合にそれを返すのに役立ちます。

ここには簡単なメモの実装があります：

// memoization takes a function as a parameter
// This function will be called every time a value is not in the cache
let memoization f =
    // The dictionary is used to store values for every parameter that has been seen
    let cache = Dictionary<_,_>()
    fun c ->
        let exist, value = cache.TryGetValue (c)
        match exist with
        | true -> 
            // Return the cached result directly, no method call
            printfn "%O -> In cache" c
            value
        | _ -> 
            // Function call is required first followed by caching the result for next call with the same parameters
            printfn "%O -> Not in cache, calling function..." c
            let value = f c
            cache.Add (c, value)
            value

memoization関数は単に関数をパラメータとして受け取り、同じシグネチャを持つ関数を返します。メソッドシグネチャf:('a -> 'b) -> ('a -> 'b)これを見ることができます。この方法で、階乗法を呼び出すのと同じ方法でメモを使用することができます。

printfn呼び出しは、関数を複数回呼び出すときに何が起こるかを示すことです。安全に取り外すことができます。

メモ帳を使うのは簡単です：

// Pass the function we want to cache as a parameter via partial application
let factorialMem = memoization factorial

// Then call the memoized function
printfn "%i" (factorialMem 10)
printfn "%i" (factorialMem 10)
printfn "%i" (factorialMem 10)
printfn "%i" (factorialMem 4)
printfn "%i" (factorialMem 4)

// Prints
// 10 -> Not in cache, calling function...
// 3628800
// 10 -> In cache
// 3628800
// 10 -> In cache
// 3628800
// 4 -> Not in cache, calling function...
// 24
// 4 -> In cache
// 24

再帰関数でのメモ帳化

整数の階乗を計算する前述の例を使用して、再帰内で計算された階乗のすべての値をハッシュ表に入れます。これは表には現れません。

memoizationに関する記事のように、関数パラメータfactと整数パラメータを受け入れる関数fを宣言します。この関数f 、 fact(n-1)からnの階乗を計算するための命令を含む。

これにより返される関数で再帰を処理することを可能にするmemorecによってではなくfact自体、おそらく場合に計算を停止fact(n-1)値が既に計算されたハッシュテーブルに配置されています。

let memorec f =
   let cache = Dictionary<_,_>()
   let rec frec n = 
       let value = ref 0
       let exist = cache.TryGetValue(n, value)
       match exist with
       | true -> 
           printfn "%O -> In cache" n
       | false ->
           printfn "%O -> Not in cache, calling function..." n
           value := f frec n
           cache.Add(n, !value)
       !value
   in frec

let f = fun fact n -> if n<2 then 1 else n*fact(n-1)

[<EntryPoint>]
let main argv = 
    let g = memorec(f)
    printfn "%A" (g 10)
    printfn "%A" "---------------------"
    printfn "%A" (g 5)
    Console.ReadLine()
    0

結果：

10 -> Not in cache, calling function...
9 -> Not in cache, calling function...
8 -> Not in cache, calling function...
7 -> Not in cache, calling function...
6 -> Not in cache, calling function...
5 -> Not in cache, calling function...
4 -> Not in cache, calling function...
3 -> Not in cache, calling function...
2 -> Not in cache, calling function...
1 -> Not in cache, calling function...
3628800
"---------------------"
5 -> In cache
120