31

f# の morris seq 用に書いたこの「学習コード」がありますが、回避方法がわからないスタック オーバーフローに悩まされています。"morris" は、無限の "see and say" シーケンス (つまり、{{1}、{1,1}、{2,1}、{1,2,1,1}、{1,1,1) を返します。 ,2,2,1}, {3,1,2,2,1,1},...})。

    let printList l =
        Seq.iter (fun n -> printf "%i" n) l
        printfn ""

    let rec morris s = 
        let next str = seq {
            let cnt = ref 1  // Stack overflow is below when enumerating
            for cur in [|0|] |> Seq.append str |> Seq.windowed 2 do
                if cur.[0] <> cur.[1] then
                    yield!( [!cnt ; cur.[0]] )
                    cnt := 0
                incr cnt
        }
        seq {
        yield s
        yield! morris (next s) // tail recursion, no stack overflow
        }

    // "main"
    // Print the nth iteration
    let _ =  [1] |> morris |> Seq.nth 3125 |> printList 

Seq.nth を使用して n 番目の反復を選択できますが、スタック オーバーフローに達する前にしか取得できません。私が持っている再帰の 1 つのビットは末尾再帰であり、本質的にリンクされた一連の列挙子を構築します。問題はそこじゃない。4000番目のシーケンスで「enum」が呼び出されたときです。F# 1.9.6.16 では、以前のバージョンは 14000 を超えていたことに注意してください)。これは、リンクされたシーケンスが解決される方法によるものです。シーケンスは遅延しているため、「再帰」も遅延しています。つまり、seq n は seq n-1 を呼び出し、seq n-2 を呼び出し、以下同様に最初の項目を取得します (最初の # が最悪のケースです)。

が問題を悪化させていることを理解しており[|0|] |> Seq.append str |> Seq.windowed 2、それを排除すれば、生成できる # を 3 倍にすることができます。実際には、コードは十分に機能します。morris の 3125 回目の反復は、長さが 10^359 文字を超えます。

私が実際に解決しようとしている問題は、遅延評価を保持し、選択できる反復のスタック サイズに基づいて制限をなくす方法です。メモリ サイズに基づいて制限を行うための適切な F# イディオムを探しています。

2010年10月更新

F# をもう少しよく学び、Haskell を少し学び、この問題を 1 年以上考え、調査した結果、ようやく自分の質問に答えることができました。しかし、難しい問題はいつもそうですが、問題は間違った質問から始まります。問題はシーケンスのシーケンスではありません。実際には、再帰的に定義されたシーケンスが原因です。私の関数型プログラミングのスキルは少し良くなったので、以下のバージョンで何が起こっているのかを簡単に確認できます。

let next str = 
    Seq.append str [0]
    |> Seq.pairwise
    |> Seq.scan (fun (n,_) (c,v) ->
            if (c = v) then (n+1,Seq.empty)
            else (1,Seq.ofList [n;c]) ) (1,Seq.empty)
    |> Seq.collect snd

let morris = Seq.unfold(fun sq -> Some(sq,next sq))

これは基本的に、シーケンスを生成するための Seq 処理関数呼び出しの非常に長いチェーンを作成します。F# に付属している Seq モジュールは、スタックを使用しないとチェーンをたどることができないものです。追加および再帰的に定義されたシーケンスに使用する最適化がありますが、その最適化は、再帰が追加を実装している場合にのみ機能します。

だからこれはうまくいく

let rec ints n = seq { yield n; yield! ints (n+1) }
printf "%A" (ints 0 |> Seq.nth 100000);;

そして、これはスタックオーバーフローを取得します。

let rec ints n = seq { yield n; yield! (ints (n+1)|> Seq.map id) }
printf "%A" (ints 0 |> Seq.nth 100000);;

F# ライブラリが問題であることを証明するために、継続を使用して追加、ペアワイズ、スキャン、および収集を実装する独自の Seq モジュールを作成しました。これで、問題なく 50,000 seq の生成と出力を開始できます (処理が終了したため、終了することはありません)。 10^5697 桁の長さ)。

いくつかの追加メモ:

  • 継続は私が探していたイディオムでしたが、この場合は、私のコードではなく、F# ライブラリに入る必要がありました。F# の継続については、Tomas Petricek の Real-World Functional Programmingの本から学びました。
  • 私が受け入れた怠惰なリストの回答は、別のイディオムを保持していました。遅延評価。書き直したライブラリでは、遅延型を利用してスタックオーバーフローを回避する必要もありました。
  • 怠惰なリストバージョンは運によって機能します(おそらく設計によるものですが、それは私の現在の判断能力を超えています)-構築および反復中に使用されるアクティブパターンマッチングにより、必要な再帰が深くなりすぎる前にリストが値を計算するため、怠惰ですが、スタックオーバーフローを避けるために継続が必要なほど怠惰ではありません。たとえば、2 番目のシーケンスが 1 番目のシーケンスの数字を必要とするときには、すでに計算されています。つまり、LL バージョンは厳密にはシーケンス生成の JIT 遅延ではなく、リスト管理のみです。
4

3 に答える 3

12

絶対にチェックした方がいい

http://research.microsoft.com/en-us/um/cambridge/projects/fsharp/manual/FSharp.PowerPack/Microsoft.FSharp.Collections.LazyList.html

しかし、後でより包括的な回答を投稿しようとします。

アップデート

わかりました、解決策は以下です。これは、モーリス シーケンスを int の LazyList の LazyList として表しています。

F# LazyList (FSharp.PowerPack.dll 内) には、次の 3 つの便利なプロパティがあります。

  • 怠惰です (n 番目の要素の評価は、最初に要求されるまで行われません)
  • 再計算しません (同じオブジェクト インスタンスの n 番目の要素を再評価しても再計算されません。最初に計算された後に各要素がキャッシュされます)。
  • プレフィックスを「忘れる」ことができます(リストに「テール」すると、参照されなくなったプレフィックスがガベージコレクションに利用可能になります)

最初のプロパティは seq (IEnumerable) と共通ですが、他の 2 つは LazyList に固有のものであり、この質問で提起されたような計算上の問題に非常に役立ちます。

コードは次のとおりです。

// print a lazy list up to some max depth
let rec PrintList n ll =
    match n with
    | 0 -> printfn ""
    | _ -> match ll with
           | LazyList.Nil -> printfn ""
           | LazyList.Cons(x,xs) ->
               printf "%d" x
               PrintList (n-1) xs

// NextMorris : LazyList<int> -> LazyList<int>
let rec NextMorris (LazyList.Cons(cur,rest)) = 
    let count = ref 1
    let ll = ref rest
    while LazyList.nonempty !ll && (LazyList.hd !ll) = cur do
        ll := LazyList.tl !ll
        incr count
    LazyList.cons !count
        (LazyList.consf cur (fun() ->
            if LazyList.nonempty !ll then
                NextMorris !ll
            else
                LazyList.empty()))

// Morris : LazyList<int> -> LazyList<LazyList<int>>
let Morris s =
    let rec MakeMorris ll =
        LazyList.consf ll (fun () ->
            let next = NextMorris ll
            MakeMorris next
        )
    MakeMorris s

// "main"
// Print the nth iteration, up to a certain depth
[1] |> LazyList.of_list |> Morris |> Seq.nth 3125 |> PrintList 10
[1] |> LazyList.of_list |> Morris |> Seq.nth 3126 |> PrintList 10
[1] |> LazyList.of_list |> Morris |> Seq.nth 100000 |> PrintList 35
[1] |> LazyList.of_list |> Morris |> Seq.nth 100001 |> PrintList 35

UPDATE2

数えたいだけなら、それも問題ありません:

let LLLength ll =
    let rec Loop ll acc =
        match ll with
        | LazyList.Cons(_,rest) -> Loop rest (acc+1N)
        | _ -> acc
    Loop ll 0N

let Main() =
    // don't do line below, it leaks
    //let hundredth = [1] |> LazyList.of_list |> Morris |> Seq.nth 100
    // if we only want to count length, make sure we throw away the only
    // copy as we traverse it to count
    [1] |> LazyList.of_list |> Morris |> Seq.nth 100
        |> LLLength |> printfn "%A" 
Main()    

メモリ使用量は横ばいです (私のボックスでは 16M 未満)... まだ実行が完了していませんが、遅いボックスでも 55 番目の長さを高速に計算したので、これで問題なく動作するはずです。これは「int」をオーバーフローすると思われるため、長さに「bignum」を使用したことにも注意してください。

于 2009-05-22T18:27:11.093 に答える
4

ここには 2 つの主な問題があると思います。

  • 遅延は非常に非効率的であるため、遅延機能の実装は桁違いに遅く実行されることが予想されます。たとえば、ここで説明する Haskell の実装は、以下に示す F# よりも 2,400 倍遅いです。回避策が必要な場合は、バッチがオンデマンドで生成される熱心なバッチにまとめて、計算を償却するのがおそらく最善の策です。

  • Seq.append関数は実際には C# コードを呼び出しているためIEnumerable、そのテール コールは排除されず、通過するたびにスタック スペースが少しずつリークします。これは、シーケンスを列挙するときに表示されます。

以下は、50 番目のサブシーケンスの長さを計算する際に実装よりも 80 倍以上高速ですが、おそらく十分に遅延しているとは言えません。

let next (xs: ResizeArray<_>) =
  let ys = ResizeArray()
  let add n x =
    if n > 0 then
      ys.Add n
      ys.Add x
  let mutable n = 0
  let mutable x = 0
  for i=0 to xs.Count-1 do
    let x' = xs.[i]
    if x=x' then
      n <- n + 1
    else
      add n x
      n <- 1
      x <- x'
  add n x
  ys

let morris =
  Seq.unfold (fun xs -> Some(xs, next xs)) (ResizeArray [1])

この関数のコアはResizeArray、構造体をアキュムレータとして使用した場合にパフォーマンスを大幅に低下させることなく、分解して機能的に使用できるフォールド オーバー a です。

于 2010-02-16T21:00:00.390 に答える
0

探していた前の要素を保存するだけです。

let morris2 data = seq {
    let cnt = ref 0
    let prev = ref (data |> Seq.nth 0)

     for cur in data do
        if cur <> !prev then
            yield! [!cnt; !prev]
            cnt := 1
            prev := cur
        else
            cnt := !cnt + 1

    yield! [!cnt; !prev]
}

let rec morrisSeq2 cur = seq {
    yield cur
    yield! morrisSeq2 (morris2 cur)
}
于 2009-05-22T19:21:46.877 に答える