带有递归调用的F#System.OutOfMemoryException

Question

这实际上是F#中Project Euler Problem 14的解决方案.但是,在尝试计算较大数字的迭代序列时,我遇到了System.OutOfMemory异常.正如您所看到的,我正在编写带尾调用的递归函数.

我遇到了StackOverFlowException的问题,因为我在visual studio中调试(禁用尾调用).我在另一个问题中记录了这一点.在这里,我正在以发布模式运行 - 但是当我将其作为控制台应用程序(在带有4gb ram的windows xp上)运行时,我的内存不足.

我真的很难理解我是如何编码自己进入内存溢出的,并希望有人能以我的方式显示我的错误.

let E14_interativeSequence x =

  let rec calc acc startNum =
    match startNum with
    | d when d = 1      -> List.rev (d::acc)
    | e when e%2 = 0    -> calc (e::acc) (e/2)
    | _                 -> calc (startNum::acc) (startNum * 3 + 1)

  let maxNum pl=

    let rec maxPairInternal acc pairList =
        match pairList with
        | []        ->  acc
        | x::xs     ->  if (snd x) > (snd acc) then maxPairInternal x xs
                        else maxPairInternal acc xs

    maxPairInternal (0,0) pl
    |> fst

  // if I lower this to like [2..99999] it will work.
  [2..99999] 
  |> List.map (fun n -> (n,(calc [] n)))
  |> List.map (fun pair -> ((fst pair), (List.length (snd pair))))
  |> maxNum
  |> (fun x-> Console.WriteLine(x))

---

编辑

根据答案的建议,我重写了使用惰性列表,并使用Int64的.

#r "FSharp.PowerPack.dll"

let E14_interativeSequence =

  let rec calc acc startNum =
    match startNum with
    | d when d = 1L         -> List.rev (d::acc) |> List.toSeq
    | e when e%2L = 0L      -> calc (e::acc) (e/2L)
    | _                     -> calc (startNum::acc) (startNum * 3L + 1L)

  let maxNum (lazyPairs:LazyList<System.Int64*System.Int64>) =

    let rec maxPairInternal acc (pairs:seq<System.Int64*System.Int64>) =
        match pairs with
        | :? LazyList<System.Int64*System.Int64> as p ->
            match p with
            | LazyList.Cons(x,xs)->  if (snd x) > (snd acc) then maxPairInternal x xs
                                     else maxPairInternal acc xs
            | _                         ->  acc
        | _ -> failwith("not a lazylist of pairs")

    maxPairInternal (0L,0L) lazyPairs
    |> fst

  {2L..999999L}
  |> Seq.map (fun n -> (n,(calc [] n)))
  |> Seq.map (fun pair -> ((fst pair), (Convert.ToInt64(Seq.length (snd pair)))))
  |> LazyList.ofSeq
  |> maxNum

这解决了这个问题.不过,我还会看看尹竺的解决方案.

Answer 1

正如Brian所说,List.*这里的操作并不合适.它们耗费了太多内存.

stackoverflow问题来自另一个地方.stackoverflow有两种可能:calc和maxPairInternal.它必须是第一个,因为第二个与第一个具有相同的深度.然后问题来自数字,问题中的数字3n+1可能很容易变得非常大.所以你首先得到一个int32溢出,然后你得到一个stackoverflow.这就是原因.将数字更改为64位后,程序可以正常工作.

这是我的解决方案页面,您可以在其中查看备忘录技巧.

open System
let E14_interativeSequence x =

  let rec calc acc startNum =
    match startNum with
    | d when d = 1L      -> List.rev (d::acc)
    | e when e%2L = 0L    -> calc (e::acc) (e/2L)
    | _                 -> calc (startNum::acc) (startNum * 3L + 1L)

  let maxNum pl=

    let rec maxPairInternal acc pairList =
        match pairList with
        | []        ->  acc
        | x::xs     ->  if (snd x) > (snd acc) then maxPairInternal x xs
                        else maxPairInternal acc xs

    maxPairInternal (0L,0) pl
    |> fst

  // if I lower this to like [2..99999] it will work.
  [2L..1000000L] 
  |> Seq.map (fun n -> (n,(calc [] n)))
  |> Seq.maxBy (fun (n, lst) -> List.length lst)
  |> (fun x-> Console.WriteLine(x))