这实际上是F#中的项目Euler Problem 14的解决方案。但是,当试图计算大数的迭代序列时,我遇到了System.OutOfMemory异常。正如你所看到的,我正在用tail调用写我的递归函数。带递归调用的F#System.OutOfMemoryException
由于我在Visual Studio中调试(禁用尾部调用),我遇到了StackOverFlowException的问题。我已经记录了in another question。在这里,我以发布模式运行 - 但是当我将其作为控制台应用程序运行时(在使用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指出的,Seq更适合这个问题。事实上,在研究Euler项目中的前45个问题后,我发现几乎所有的问题都适用于基于Seq的解决方案。如果你有兴趣,这是我对问题14的解决方案:http://projecteulerfun.blogspot.com/2010/05/problem-14-which-starting-number-under.html(当然,你可能想等待直到你将你的工作满意为止,或者你可能已经满足于你的算法,但希望看到基于Seq的实现的外观)。 – 2010-11-09 00:50:52
警告,除了OutOfMemoryException外,还有至少一个其他问题,您的解决方案可能会因查看我的解决方案而被破坏。 – 2010-11-09 00:53:24