recursion - F# System.OutOfMemoryException 与递归调用

Question

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

我遇到了 StackOverFlowException 的问题，因为我正在 Visual Studio 中进行调试(这会禁用尾部调用)。我已经记录了 in another question 。在这里，我在 Release模式下运行 - 但当我将其作为控制台应用程序运行时(在具有 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

解决了这个问题。不过，我也会看看 Yin Zhu 的解决方案，它更好。

Answer 1

正如 Brian 所提到的，List.* 操作在这里不合适。它们消耗了太多的内存。

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

Here is my solution page ，您可以在其中看到内存技巧。

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