帶遞歸調用的F＃System.OutOfMemoryException

Question

這實際上是F＃中的項目Euler Problem 14的解決方案。但是，當試圖計算大數的迭代序列時，我遇到了System.OutOfMemory異常。正如你所看到的，我正在用tail調用寫我的遞歸函數。

由於我在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的解決方案更好。

Answer 1

正如Brian所說，List.*操作在這裏並不合適。他們花費太多的內存。

該stackoverflow問題來自另一個地方。有兩種可能有你的計算器：calc和maxPairInternal。它必須是第一個，因爲第二個與第一個深度相同。那麼問題來了，這個數字在3n+1的問題很容易就會變得很大。所以你首先得到一個int32溢出，然後你得到一個stackoverflow。這就是原因。將數字更改爲64位後，該程序起作用。

Here is my solution page，在那裏你可以看到一個memoization技巧。

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

Answer 2

如果將List.map更改爲Seq.map（並且重新工作maxPairInternal以迭代seq），這可能會幫助噸。現在，在處理整個結構以獲得單個數字結果之前，您將在一個巨大的結構中同時顯示所有數據。通過Seq懶洋洋地做這件事情要好得多，只需創建一行，並將其與下一行進行比較，然後一次創建一行，然後丟棄它。

我現在沒有時間編寫我的建議，但是如果您仍然遇到問題，請告訴我，我會重新審視這個問題。

Answer 3

不要試圖在任何地方使用列表，這不是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秒。

Answer 4

找到了這個尋找Microsoft.FSharp.Core.Operators.Checked。 我剛剛學習F＃，所以我想我會參加歐拉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