代码之家 › 专栏 › 技术社区 › Kevin Won

带有递归调用的F System.OutOfMemoryException

tail-recursion out-of-memory f# recursion

Kevin Won · 技术社区 · 15 年前

这实际上是项目Euler的解决方案 Problem 14 在F。但是,当我试图为更大的数字计算迭代序列时,遇到System.OutofMemory异常。如您所见,我正在编写带有尾部调用的递归函数。

我遇到StackOverflowException的问题,因为我在Visual Studio中调试(它禁用尾调用)。我已经记录了 in another question . 这里,我是在发布模式下运行的——但是当我作为控制台应用程序(在带有4GB内存的WindowsXP上)运行这个应用程序时,内存不足异常。

我真的茫然不知所措,无法理解自己是如何将自己编码成内存溢出的,希望有人能用我的方式来显示我的错误。

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

这就解决了问题。我也会看一看殷朱的解决方案,那是更好的。

4 回复 | 直到 9 年前

Yin Zhu 15 年前

正如布莱恩所说, 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))

Brian 15 年前

如果您将list.map更改为seq.map(并重新工作maxpairenternal以迭代seq),这可能会帮助吨。现在,在处理整个结构以获得单个数字结果之前,您将在一个巨大的结构中同时显示所有数据。最好是通过SEQ懒洋洋地这样做,只需创建一行,并与下一行进行比较,然后一次创建一行,然后丢弃它。

我现在没有时间对我的建议进行编码,但是如果您仍有问题,请告诉我,我将重新讨论这个问题。

J D 15 年前

别到处使用列表了,这不是哈斯克尔!停止写作 fst pair 和 snd pair 到处都是,这不是口齿不清!

如果您希望在f中有一个简单的解决方案,您可以直接这样做,而无需创建任何中间数据结构:

let rec f = function
  | 1L -> 0
  | n when n % 2L = 0L -> 1 + f(n / 2L)
  | n -> 1 + f(3L * n + 1L)

let rec g (li, i) = function
  | 1L -> i
  | n -> g (max (li, i) (f n, n)) (n - 1L)

let euler14 n = g (0, 1L) n

我上网本大概需要15秒。如果需要更省时的方法,请通过数组重新使用以前的结果:

let rec inside (a : _ array) n =
  if n <= 1L || a.[int n] > 0s then a.[int n] else
    let p =
      if n &&& 1L = 0L then inside a (n >>> 1) else
        let n = 3L*n + 1L
        if n < int64 a.Length then inside a n else outside a n
    a.[int n] <- 1s + p
    1s + p
and outside (a : _ array) n =
  let n = if n &&& 1L = 0L then n >>> 1 else 3L*n + 1L
  1s + if n < int64 a.Length then inside a n else outside a n

let euler14 n =
  let a = Array.create (n+1) 0s
  let a = Array.Parallel.init (n+1) (fun n -> inside a (int64 n))
  let i = Array.findIndex (Array.reduce max a |> (=)) a
  i, a.[i]

我的上网本大约需要0.2秒。

chuckc 9 年前

在查找microsoft.fsharp.core.operators.checked时找到此。我只是在学习F,所以我想我会接受项目Euler 14挑战。

它使用递归,但不使用尾部递归。我用了大约3.1秒,但有一个优势,我几乎可以理解它。

let Collatz (n:int64) = if n % 2L = 0L then n / 2L else n * 3L + 1L

let rec CollatzLength (current:int64) (acc:int) =
    match current with 
    | 1L -> acc
    | _ -> CollatzLength (Collatz current) (acc + 1)

let collatzSeq (max:int64) = 
    seq{
        for i in 1L..max do
            yield i, CollatzLength i 0
    }

let collatz = Seq.toList(collatzSeq 1000000L)

let result, steps = List.maxBy snd collatz