F＃Seqの実装上の問題

Question

最近F＃ソースコードを掘り下げています。 Seq.fsで

：最初のものは非常に高速である

let rec rwalk n = seq { if n > 0 then 
         yield n 
         yield! rwalk (n-1) 
         } 

と

let rec rwalk n = seq { if n > 0 then 
         yield! rwalk (n-1) 
         yield n 
         } 

は、私が見つけた：

// Binding. 
// 
// We use a type defintion to apply a local dynamic optimization. 
// We automatically right-associate binding, i.e. push the continuations to the right. 
// That is, bindG (bindG G1 cont1) cont2 --> bindG G1 (cont1 o cont2) 
// This makes constructs such as the following linear rather than quadratic: 
// 
// let rec rwalk n = { if n > 0 then 
//       yield! rwalk (n-1) 
//       yield n } 

上記のコードを見た後、私は2つのコードをテスト、2番目は非常に遅いです。 n = 10000の場合、このシーケンスを生成するために私のマシンでは3秒かかります。つまり2次の時間です。

二次的な時間は合理的です。

seq { yield! {1; 2; ...; n-1}; yield n }は私が推測する、線形時間を取る必要があります

Seq.append {1; 2; ...; n-1} {n} 

この追加操作に変換されます。最初のコードでは、追加操作は次のようになります：seq { yield n; yield! {n-1; n-2; ...; 1} }、一定の時間がかかります。

コード内のコメントは、それがlinear（多分この線形は線形時間ではない）であると言う。おそらく、linearは、Moand/F＃計算式ではなく、シーケンスのカスタマイズされた実装を使用することに関連しています（F＃仕様で述べられていますが、その理由は言及していません...）。

ここではあいまいさを明確にすることはできますか？どうもありがとう！

（これは、言語の設計と最適化問題であるPSので、私もそこに人々が洞察力を持っているかどうかを確認するためにHaskellのタグを添付。）

Answer 1

とき非末尾呼び出し位置でyield!表示され、それがessentiall同じことを意味します

for v in <expr> do yield v 

をこれに伴う問題（とその次である理由は）再帰呼び出しのために、これは、ネストされたループを有するforイテレータのチェーンを作成することです。単一の要素ごとに<expr>によって生成されたシーケンス全体を反復処理する必要があります。繰り返しが線形の場合、線形反復がすべての要素で発生するため、二次的な時間が得られます。

rwalk関数が[ 9; 2; 3; 7 ]を生成するとします。最初の反復では、再帰的に生成されたシーケンスには4つの要素があるので、4つの要素を反復して1を追加します。再帰呼び出しでは、3つの要素を反復して1などを追加します。それは二次ですどのように参照してください。

x 
x x 
x x x 
x x x x 

また、再帰呼び出しのそれぞれは、オブジェクト（IEnumerator）の新しいインスタンスを作成しますので、いくつかのメモリコストは（のみ線形が）もあります。

テールコールポジションのでは、F＃コンパイラ/ライブラリが最適化を行います。現在のIEnumerableを再帰呼び出しによって返されたものに「置き換える」ので、すべての要素を生成するために過度の反復処理を行う必要はありません。単純に返されます（メモリコストも削除されます）。

関連する。同じ問題がC＃lanaugageデザインで説明されており、interesting paper about it（yield!の名前はyield foreachです）があります。

Answer 2

あなたが探している回答の種類がわかりません。ご存じのように、このコメントはコンパイラの動作と一致しません。私はこれが実装と同期していないコメントのインスタンスかどうか、それが実際にはパフォーマンスのバグかどうかは言えません（たとえば、仕様は特定のパフォーマンス要件を呼び出すようには見えません）。

しかし、理論的には、コンパイラの機械が、あなたの例を線形時間で処理する実装を生成することは可能であるべきです。実際には、計算式を使ってそのような実装をライブラリに構築することさえ可能です。ここでは、主にトーマスは引用論文に基づいてラフたとえば、です：私のSeqBuilderは堅牢ではありません

open System.Collections 
open System.Collections.Generic 

type 'a nestedState = 
/// Nothing to yield 
| Done 
/// Yield a single value before proceeding 
| Val of 'a 
/// Yield the results from a nested iterator before proceeding 
| Enum of (unit -> 'a nestedState) 
/// Yield just the results from a nested iterator 
| Tail of (unit -> 'a nestedState) 

type nestedSeq<'a>(ntor) = 
    let getEnumerator() : IEnumerator<'a> = 
    let stack = ref [ntor] 
    let curr = ref Unchecked.defaultof<'a> 
    let rec moveNext() = 
     match !stack with 
     | [] -> false 
     | e::es as l -> 
      match e() with 
      | Done -> stack := es; moveNext() 
      | Val(a) -> curr := a; true 
      | Enum(e) -> stack := e :: l; moveNext() 
      | Tail(e) -> stack := e :: es; moveNext() 
    { new IEnumerator<'a> with 
     member x.Current = !curr 
     interface System.IDisposable with 
     member x.Dispose() =() 
     interface IEnumerator with 
     member x.MoveNext() = moveNext() 
     member x.Current = box !curr 
     member x.Reset() = failwith "Reset not supported" } 
    member x.NestedEnumerator = ntor 
    interface IEnumerable<'a> with 
    member x.GetEnumerator() = getEnumerator() 
    interface IEnumerable with 
    member x.GetEnumerator() = upcast getEnumerator() 

let getNestedEnumerator : 'a seq -> _ = function 
| :? ('a nestedSeq) as n -> n.NestedEnumerator 
| s -> 
    let e = s.GetEnumerator() 
    fun() -> 
     if e.MoveNext() then 
     Val e.Current 
     else 
     Done 

let states (arr : Lazy<_[]>) = 
    let state = ref -1 
    nestedSeq (fun() -> incr state; arr.Value.[!state]) :> seq<_> 

type SeqBuilder() = 
    member s.Yield(x) = 
    states (lazy [| Val x; Done |]) 
    member s.Combine(x:'a seq, y:'a seq) = 
    states (lazy [| Enum (getNestedEnumerator x); Tail (getNestedEnumerator y) |]) 
    member s.Zero() = 
    states (lazy [| Done |]) 
    member s.Delay(f) = 
    states (lazy [| Tail (f() |> getNestedEnumerator) |]) 
    member s.YieldFrom(x) = x 
    member s.Bind(x:'a seq, f) = 
    let e = x.GetEnumerator() 
    nestedSeq (fun() -> 
       if e.MoveNext() then 
        Enum (f e.Current |> getNestedEnumerator) 
       else 
        Done) :> seq<_> 

let seq = SeqBuilder() 

let rec walkr n = seq { 
    if n > 0 then 
    return! walkr (n-1) 
    return n 
} 

let rec walkl n = seq { 
    if n > 0 then 
    return n 
    return! walkl (n-1) 
} 

let time = 
    let watch = System.Diagnostics.Stopwatch.StartNew() 
    walkr 10000 |> Seq.iter ignore 
    watch.Stop() 
    watch.Elapsed 

注;いくつかのワークフローメンバーが不足していて、オブジェクトの廃棄やエラー処理に関して何もしません。ただし、SequenceBuilderがでないと、は、あなたのような例で二次的な実行時間を表示する必要があります。

walkr nのネストされたイテレータは、O（n）時間内にシーケンスを反復処理しますが、そのためにはO（n）スペースが必要です。