2

これは、実際には F# のProject Euler Problem 14のソリューションです。ただし、より大きな数値の反復シーケンスを計算しようとすると、System.OutOfMemory 例外が発生します。ご覧のとおり、テール コールを使用して再帰関数を記述しています。

ビジュアルスタジオでデバッグしていたため（テールコールが無効になっているため）、StackOverFlowExceptionで問題が発生していました。別の質問でそれを文書化しました。ここでは、リリース モードで実行していますが、これをコンソール アプリとして実行すると、メモリ不足の例外が発生します (Windows XP 上で 4 GB RAM を使用)。

このメモリオーバーフローに自分自身をどのようにコーディングしたかを理解するのに本当に途方に暮れており、誰かが私の方法でエラーを示してくれることを望んでいます。

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

問題を解決します。ただし、より優れたYin Zhuのソリューションも検討します。

4

4 に答える 4

6

ブライアンが述べたように、List.*ここでは操作は適切ではありません。それらはメモリを大量に消費します。

スタックオーバーフローの問題は別の場所から発生します。スタックオーバーフローが発生する可能性があるのは、 と の 2 つcalcですmaxPairInternal。2 番目の深さは 1 番目と同じであるため、1 番目でなければなりません。次に、問題は数字になります3n+1。問題の数字は簡単に非常に大きくなる可能性があります。したがって、最初に int32 オーバーフローが発生し、次にスタックオーバーフローが発生します。それが理由です。数値を 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 を介してこれを遅延して行う方がはるかに優れています。1 つの行を作成し、それを次の行と比較し、一度に 1 つの行を作成してから破棄します。

今は私の提案をコーディングする時間がありませんが、まだ問題がある場合はお知らせください。もう一度検討します。

于 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 に答える