如何从值数组中记忆一个函数

Question

拿

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

然后

let f (x:array<_>) = x.Length

然后

let g = memoization f
let a = g [|1|]
let b = g [|1|]

我（显然！）希望 b 是检索到的已计算的记忆值，但它重新计算了它。

好吧，很公平，有 C# 头，这是有道理的，我们又回到了讨厌的对象，那么我如何记住一个采用值数组的函数？

我注意到列表很好用那么数组有什么特别之处呢？

Answer 1

问题是，默认情况下，Dictionary 使用引用相等性来检查对象是否在字典中。这意味着它只有在您将相同的数组实例传递给它时才会起作用。下面从缓存中获取值：

let g = memoization f
let arr = [|1|]
let a = g arr
let b = g arr

如果你想根据数组中的值来记忆结果，你可以改用结构相等比较。为此，您需要做的就是将 HashIdentity.Structural 作为参数传递给 Dictionary。这使用 F# 库定义的结构比较，returns 包含相同值的数组的相同散列：

let cache = Dictionary<_,_>(HashIdentity.Structural)

进行此更改后，您的原始示例将如您所愿地工作。

如何从值数组中记忆一个函数

how to memoize a function from an array of values

f#