2

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

我遇到了 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

这解决了这个问题。不过，我也会看看殷朱的解决方案，哪个更好。

4

4 回答 4

6

正如布赖恩所提到的，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))
于 2010-11-09T01:18:02.417 回答
4

如果您将 List.map 更改为 Seq.map（并重新处理 maxPairInternal 以迭代 seq），这可能会有所帮助。现在，在处理整个结构以获得单个数字结果之前，您正在将所有数据一次显示在一个巨大的结构中。最好通过 Seq 懒惰地执行此操作，只需创建一行，然后将其与下一行进行比较，一次创建一行然后丢弃它。

我现在没有时间编写我的建议，但是如果您仍然遇到问题，请告诉我，我会重新考虑。

于 2010-11-08T22:31:16.303 回答
2

停止尝试在任何地方使用列表，这不是 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 秒。

于 2010-11-13T14:29:34.290 回答
0

发现这个正在寻找 Microsoft.FSharp.Core.Operators.Checked。我刚刚学习 F#，所以我想我会参加 Project 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
于 2017-07-13T04:32:40.320 回答