2

シーケンスの最初の要素をリストに再帰的に追加することにより、シーケンスからリストを構築しようとしています:

open System


let s = seq[for i in 2..4350 -> i,2*i]

let rec copy s res = 
     if  (s|>Seq.isEmpty)  then 
         res
     else
         let (a,b) = s |> Seq.head
         Console.WriteLine(string a)
         let newS = s |> Seq.skip(1)|> Seq.cache
         let newRes = List.append res ([(a,b)])
         copy newS newRes



copy s ([])

2 つの問題:

. スタック オーバーフローが発生しました。これは、テール リカッシブな策略がひどい

. |> Seq.cacheここ に置くと、コードが 100 倍高速になるのはなぜですかlet newS = s |> Seq.skip(1)|> Seq.cache

(これはほんの少しの演習であることに注意してください。Seq.toList などを実行できることは理解しています。)

どうもありがとう

機能する1つの方法は次のとおりです(2つのポイントはまだ私には少し奇妙です):

let toList (s:seq<_>) =

    let rec copyRev res (enum:Collections.Generic.IEnumerator<_*_>) = 
         let somethingLeft = enum.MoveNext()
         if  not(somethingLeft)  then 
             res
         else
             let curr = enum.Current
             Console.WriteLine(string curr)
             let newRes = curr::res
             copyRev newRes enum

    let enumerator = s.GetEnumerator()
    (copyRev ([]) (enumerator)) |>List.rev
4

4 に答える 4

3

あなたはそれがただの練習だと言いますが、私の答えを指摘することは役に立ちます

F# の while または末尾再帰、いつ何を使用するか?

可能であれば、より適用的/宣言的な構造を優先する必要があることを繰り返します。例えば

let rec copy2 s = [
    for tuple in s do
        System.Console.WriteLine(string(fst tuple))
        yield tuple
    ]

は、特定の機能を表現する優れたパフォーマンスの高い方法です。

とはいえ、「そんなに大きなリストを作るな」とも言わないと気が済まない。巨大なデータの場合は、配列または配列のいずれかが必要です。

于 2010-08-17T14:25:14.340 に答える
1

F# に関する私の短い経験でSeq.skip 1は、テール付きのリストのように使用することはお勧めできません。n をスキップするだけでなくSeq.skip、新しいものを作成します。IEnumerable/sequenceしたがって、関数は よりも大幅に遅くなりList.toSeqます。あなたはそれを適切に行うべきです

s.GetEnumerator()

シーケンスを反復し、すべての要素をコンスするリストを保持します。

この質問では

F# で N 個の異なるインデックスを持つシーケンスから N 個の要素を取得する

私はあなたがしていることと似たようなことを始めましたが、それが非常に遅いことがわかりました. それを行う方法については、インスピレーションを得るための私の方法を参照してください。

追加:私はこれを書きました:

let seqToList (xs : seq<'a>) =
    let e = xs.GetEnumerator()
    let mutable res = []

    while e.MoveNext() do
        res <- e.Current :: res

    List.rev res

そして、ビルドインメソッドが実際に非常によく似たことを行うことがわかりました(逆の部分を含む)。ただし、指定したシーケンスが実際にリストまたは配列であるかどうかはチェックされます。

コードを完全に機能させることができます:(私も今やりました-抵抗できませんでした;-))

let seqToList (xs : seq<'a>) =
        Seq.fold (fun state t -> t :: state) [] xs |> List.rev
于 2010-08-17T13:59:02.057 に答える
1

あなたの関数は適切に末尾再帰的であるため、再帰呼び出し自体はスタックをオーバーフローしているものではありません。代わりに、問題は、Seq.skip他の人が指摘しているように、再帰的に使用すると動作が悪いことです。たとえば、このコードは私のマシンのスタックをオーバーフローさせます:

let mutable s = seq { 1 .. 20001 }
for i in 1 .. 20000 do
  s <- Seq.skip 1 s
let v = Seq.head s

おそらく、あなた自身のコードへのあいまいなつながりを見ることができます。これはSeq.skip 1、最初のシーケンスに繰り返し適用した結果、最終的にはシーケンスの先頭になります。

于 2010-08-17T15:13:43.353 に答える
0

次のコードを試してください。

警告: このコードを実行する前に、Visual Studio でテール コールの生成を有効にする必要があります。これは、プロジェクト プロパティ ページの [ビルド] タブから実行できます。これが有効になっていない場合、コードは継続を処理する StackOverflow になります。

open System
open System.Collections.Generic

    let s = seq[for i in 2..1000000 -> i,2*i]

    let rec copy (s : (int * int) seq) = 
        use e = s.GetEnumerator()
        let rec inner cont =
            if e.MoveNext() then 
                let (a,b) = e.Current
                printfn "%d" b
                inner (fun l -> cont (b :: l))
            else cont []
        inner (fun x -> x)

    let res = copy s 
    printfn "Done"
于 2010-08-17T14:05:59.240 に答える