F# 记忆效率 - 近 100 万个元素

Question

我正在研究 this problem 的 f# 解决方案，我需要在其中找到生成序列最长的 1,000,000 以上的生成器元素我使用尾递归函数来记忆以前的结果以加快计算速度。这是我当前的实现。

let memoize f = 
        let cache = new Dictionary<_,_>(1000000)
        (fun x ->
            match cache.TryGetValue x with
            | true, v -> 
                v
            | _ -> let v = f x
                   cache.Add(x, v)
                   v)

let rec memSequence =
        memoize (fun generator s ->
            if generator = 1 then s + 1
            else
                let state = s+1
                if even generator then memSequence(generator/2) state
                else memSequence(3*generator + 1) state   )

let problem14 =
        Array.init 999999 (fun idx -> (idx+1, (memSequence (idx+1) 0))) |> Array.maxBy snd |> fst

在想要计算由前 100,000 个数字生成的序列的长度之前，它似乎运行良好，但速度明显变慢。事实上，对于 120,000，它似乎并没有终止。我有一种感觉，这可能是由于我使用的词典，但我读到这不应该是这种情况。您能否指出为什么这可能效率低下？

Answer 1

您走在正确的轨道上，但是在实现记忆化的方式上有一点非常错误。

你的 memoize 函数接受一个参数的函数和 returns 它的一个记忆版本。然而，当你在 memSequence 中使用它时，你给它一个柯里化的、两个参数的函数。然后发生的是 memoize 获取函数并保存仅对第一个参数部分应用它的结果，即它存储将函数应用到 generator 所产生的闭包，然后继续调用这些闭包s。

这意味着您的记忆实际上没有做任何事情 - 在您的记忆函数中添加一些打印语句，您会发现您仍在进行完全递归。

Answer 2

我认为潜在的问题可能是 如何将记忆函数与需要多个参数的可能代价高昂的计算函数结合起来？。在这种情况下，不需要第二个参数。 memoizing 2168612个元素（计算后字典的大小）本质上没有错。

注意溢出，因为在 113383 处序列超过 System.Int32.MaxValue。因此，解决方案可能如下所示：

let memoRec f =
    let d = new System.Collections.Generic.Dictionary<_,_>()
    let rec g x =
        match d.TryGetValue x with
        | true, res -> res
        | _ -> let res = f g x in d.Add(x, res); res
    g

let collatzLong =
    memoRec (fun f n ->
        if n <= 1L then 0
        else 1 + f (if n % 2L = 0L then n / 2L else n * 3L + 1L) )

{0L .. 999999L}
|> Seq.map (fun i -> i, collatzLong i)
|> Seq.maxBy snd
|> fst

F# 记忆效率 - 近 100 万个元素

F# memoization efficiency - near 1 million elements

arrays

performance

f#

dictionary