簡單的記憶

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 實現:

// 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) 中看到這個。這樣你就可以像呼叫階乘方法一樣使用 memoization。

printfn 呼叫將顯示當我們多次呼叫該函式時會發生什麼; 它們可以安全地移除。

使用 memoization 很容易:

// 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