3

これらの 2 つのスレッドを見た後: F# には Haskell のテイクと同等のものがありますか? 、F# で N 個の異なるインデックスを持つシーケンスから N 個の要素を取得 します 、リストでシーケンス演算子を使用する最良の方法、またはそれらを使用する場合でも、

私は現在 F# の初心者であり、HtmlAgilityPack から取得した多くのシーケンスを処理する必要があるプログラムを作成しています。Seq モジュールには興味深い演算子がいくつかありますが、それらのスレッドで述べられているように、パフォーマンスに関連して不十分である可能性があり、seq -> list の間で常に変換する必要がある場合、問題解決ではないものでコードが乱雑になります.. . それが最初に F# を学び始めた理由です。

簡単な例は、リストの「N」個の要素を取得する必要がある場合です。

               listOfRows
               |> Seq.take 2
               // Now I don't have a list anymore, it returns a sequence
               |> List.ofSeq

では、これらのシナリオに対処する最善の方法について誰かが光を当てることができますか? Seq.take と Seq.skip を使用してソリューションを実行できますが、これは非常に非効率的であることが知られています。一方、機能を標準ライブラリに組み込み、別のコレクションで同じ概念を使用するために再実装したり、明示的な変換でコードを汚したりするのは残念です。

「list -> seq」と「seq -> list」の間の各変換がパフォーマンスに与える影響をどのように確認できますか?

どうもありがとう。

4

5 に答える 5

6

これらの実装はかなり簡単です。

module List =

  let take n items =
    let rec take' acc = function
      | 0, _ -> List.rev acc
      | _, [] -> invalidOp "count exceeds number of elements"
      | n, h::t -> take' (h::acc) (n-1, t)
    take' [] (n, items)

  let rec skip n items =
    match n, items with
    | 0, _ -> items
    | _, [] -> invalidOp "count exceeds number of elements"
    | n, _::t -> skip (n-1) t

そして、これが彼らのパフォーマンスと彼らのSeqカウンターパートです.

let n = 10000000
let l = List.init n id
let test f = f (n-1) l

test List.take               //Real: 00:00:03.724, CPU: 00:00:03.822, GC gen0: 57, gen1: 34, gen2: 1
test Seq.take |> Seq.toList  //Real: 00:00:04.953, CPU: 00:00:04.898, GC gen0: 57, gen1: 33, gen2: 0
test List.skip               //Real: 00:00:00.044, CPU: 00:00:00.046, GC gen0: 0, gen1: 0, gen2: 0
test Seq.skip |> Seq.toList  //Real: 00:00:01.147, CPU: 00:00:01.154, GC gen0: 0, gen1: 0, gen2: 0

アプリケーションでミリ秒が重要な場合は、「不足している」List関数を作成する価値があるかもしれません。それ以外の場合は、Seqバージョンを使用してもまったく問題ありません。

于 2011-09-15T02:28:58.083 に答える
3

これの一部は、このすべてをエンドツーエンドでどのように使用したいかによって異なります。

多くの場合、事前にリストに変換してから、リスト演算子のみを使用してマップ/トラバース/などを行うことで問題ありません。は存在しないかもしれませんがList.take、それは、リストでは、少なくとも 2 つの要素があることがわかっていて、それらの 2 つを取得したい場合、パターン マッチでそれを実行できるためです。

let (item1::item2::rest) = someList

だから私はそれがこのシナリオであなたがしたいことかもしれないと思います（私はHTML解析で期待しています、あなたが探している要素の大まかなスキーマなどを期待しているかもしれません）。

(怠惰/ストリーミングが不可欠な場合、Seq はより便利になります。)

簡単に言うと、最も一般的な演算子 ( などmap) はすべてのコレクション型 ( Seq、List、Array、...) で使用できますが、一般的でないもの ( などtake) は Seq でのみ使用できます。 (たとえば、最初の項目を取得するためのリスト パターン マッチング)。

于 2011-09-15T00:33:19.810 に答える
2

変換 Seq -> List および List -> Seq のパフォーマンスへの影響は、対応する変換の実装を調べることで完全に理解できます。

// List.ofSeq
let ofSeq source = Seq.toList source
// List.toSeq
let toSeq list = Seq.ofList list
// Seq.ofList
let ofList (source : 'T list) = 
        (source :> seq<'T>)
// Seq.toList
let toList (source : seq<'T>) = 
        checkNonNull "source" source
        match source with 
        | :? ('T list) as res -> res
        | :? ('T[]) as res -> List.ofArray res
        | _ -> 
            use e = source.GetEnumerator()
            let mutable res = [] 
            while e.MoveNext() do
                res <- e.Current :: res
            List.rev res

コレクションに対する実際の操作と比較すると、変換自体のパフォーマンスは比較的低くなります。私の古いCore 2 Duo 2.4Ghzノートブックで、100万人のメンバーのリストをseqに変換してから別のリストに戻す次のスニペットを実行します

open System.Diagnostics

let tls = Stopwatch()
let l = [1..1000000]
tls.Start()
let s = List.toSeq l
//Seq.length s |> ignore
//Seq.length s |> ignore
tls.Stop()
printfn "List<int> of 1000000 -> Seq: %d ticks" tls.ElapsedTicks 

let tsl = Stopwatch()
tsl.Start()
let l' = Seq.toList s
//l'.Length |> ignore
//l'.Length |> ignore
tsl.Stop()
printfn "Seq<int> of 1000000 -> List: %d ticks" tsl.ElapsedTicks

ブラスト 42 と 8 ティックが対応して表示されます。長さカウンターを含む最初のそれぞれの行のコメントを外すと、実行には 18695 ティックと 12952 ティックがかかります。長さカウンターを含む 2 番目のそれぞれの行のコメントを外した後、実行時間は 38377 および 25404 ティックを示しています。これは、怠惰が観測された現象とは無関係であることを示しています。

Seq 型と List 型の間の変換のオーバーヘッドは、コレクション操作の実行自体と比較して無視できるようです。

于 2011-09-15T03:55:27.690 に答える
2

コメントを追加するには

純粋に機能的な意味takeで、その場でリストを操作することはできません - 考慮してください

a::b::c::d::[]

最初の 2 つの要素だけが必要な場合は、少なくとも次のように変更する必要がありbます。

a::b::[]

が変更されたため、新しい modified を指すようbに変更する必要もあります。この結果、リストに take in place を実装することは不可能であり、これがモジュールにない理由を説明しています。abList

パフォーマンスが本当に心配な場合は、最初にプロファイルを作成してから、別のデータ型に切り替えることを検討してください。とSystem.Collections.Generic.List<_>同じメソッドの多くを持つ.Netを使用する方が良いかもしれません- http://research.microsoft.com/en-us/um/cambridge/projects/fsharp/manual/fsharp.powerpack/microsoft.fsharp .collections.resizearray.htmlListArray

于 2011-09-15T00:55:02.483 に答える
1

List to Seq は、リストにイテレータ (.net の世界では Enumerable) を作成することに他ならないため、基本的には、パフォーマンスの問題の多くを引き起こす操作ではありません (状態を保持するステート マシンを作成するだけです)。 'yield' にする必要があるリスト内の現在の要素と、より多くの要素が要求されるにつれて増加する)。一方、Seq (値を生成する基となるコレクションを持つ) を List に変換することは、概念的には、リストを反復してそこから新しいリストを作成することと同じであるため、時間とメモリを消費するプロセスになる可能性があります。リストは十分に長いです。

これらの演算子の使用法に関する限り、考えられるアプローチの 1 つは、すべてのシーケンス演算子をグループ化することです (コレクション要素が 1 つずつ処理されるパイプラインを作成する linq クエリと同じです)。リストはすべてのフィルタリング、マッピング、テイクなどの最後に作成され、最終データの準備ができたらリストに変換するため、結果の Seq からリストを作成する必要があります。中間リストを作成するとうまくいかず、パフォーマンスの問題が発生します。

于 2011-09-15T04:12:00.860 に答える