带递归调用的F＃System.OutOfMemoryException
这实际上是F＃中的项目欧拉问题14的解决方案。 但是，当试图计算大数的迭代序列时，我遇到了System.OutOfMemory异常。 正如你所看到的，我正在用tail调用写我的递归函数。
我遇到了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
解决了这个问题。 尽管如此，我也会看到尹's的解决方案更好。
正如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))
如果将List.map更改为Seq.map（并且重新设置maxPairInternal以遍历seq），这可能会帮助您解决问题。 现在，在处理整个结构以获得单个数字结果之前，您将在一个巨大的结构中同时显示所有数据。 通过Seq懒洋洋地做这件事情要好得多，只需创建一行，并将其与下一行进行比较，然后一次创建一行，然后丢弃它。
我现在没有时间对我的建议进行编码，但是如果您仍然遇到问题，请告诉我，我会重新讨论这个问题。
不要试图在任何地方使用列表，这不是Haskell！ 并且不要在任何地方写fst pair和snd pair ，这不是Lisp！
如果你想在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秒。
链接地址: http://www.djcxy.com/p/80587.html