F＃リストとシーケンス演算子

Question

Does F# have an equivalent to Haskell's take?,Take N elements from sequence with N different indexes in F# の2つのスレッドを見てから、シーケンス演算子をリストに使用する最良の方法について考えています。

私は現時点で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'間の各変換にどのような影響がありますか？

ありがとうございます。

Answer 1

これは、このエンドツーエンドのすべてをどのように使いたいかによって決まる場合があります。

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

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

だから私は（私はあなたが探している要素の予想ラフスキーマなどのいくつかの種類を持っているかもしれませんが、HTMLの構文解析と期待して）あなたは、このシナリオで何をしたいことができることを疑います。

（怠惰/ストリーミングが不可欠である場合には、配列がはるかに便利になります。）

簡単に言えば、最も一般的な演算子（のようなmap）は、すべてのコレクション型（Seq、List、Array、...）であります（takeのような）珍しいものは、具体的なタイプ（例えば、最初のアイテムを取るためのリストパターンマッチング）があるときに、より良いやり方があるので、しばしばSeqでしか利用できません。

Answer 2

takeが所定の場所にリストを操作することはできません純粋に機能的な意味でコメント

を追加するには - 考える

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

我々は唯一の最初の2つの要素が必要な場合は、我々は非常に、少なくともする必要が我々は

a::b::[] 

を得るようにbを変更bが変更されたので、あなたもを変更する必要があります新しい変更されたbを指し示すように。この結果、リストにテイクを実装することは不可能であり、これはなぜそれがListモジュールから欠落しているのかを説明します。

パフォーマンスが本当に心配な場合は、まずプロファイルを作成してから、別のデータタイプに切り替えることを検討してください。これらは、実装がかなり些細ですhttp://research.microsoft.com/en-us/um/cambridge/projects/fsharp/manual/fsharp.powerpack/microsoft.fsharp.collections.resizearray.html

Answer 3

- あなたはListとArrayと同じ方法の多くを持っているネットSystem.Collections.Generic.List<_>を使用したほうが良いかもしれません。

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バージョンを使用して完全に上質だと言うでしょう。

Answer 4

あなたが完全に変換配列のパフォーマンスへの影響を理解することができる - >リストとリスト - >配列に対応する変換の実装を調べて：コレクション上の実際の動作と比較した場合、その人自身がパフォーマンスに比較的軽い

// 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のノートcorrespondently 42と8ティックブラスト

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 

番組に別のリストに戻って、その後、配列に100万人のメンバーのリストを変換し、次のスニペットを実行します。長さカウンタを持つ最初の行のコメントを外すと、実行には18695と12952ティックがかかります。長さカウンタの第2のそれぞれの行のコメントを外した後、実行時間は38377と25404ティックを示し、これは怠惰が観察されたフェノメナと無関係であることを示します。

SeqとListの間の変換のオーバーヘッドは、Collections操作の実行そのものと比べて無視できるようです。

Answer 5

Listは、リストのイテレータ（.net world a Enumerable）を作成することに過ぎません。基本的に、パフォーマンスの問題を引き起こすような操作ではありません。リストの現在の要素が「yield」である必要があり、より多くの要素が要求されたときにその要素をインクリメントする状態）を示します。一方、Seq（値を生成する基本的なコレクションを持つ）をListに変換することは、概念的にはリストを反復してそれから新しいリストを作成するのと同じです。したがって、時間とメモリを消費するプロセスかもしれませんリストは十分に長いです。

これらの演算子の使い方は、すべてのシーケンス演算子をグループ化することです（コレクション要素を1つずつ処理するパイプラインを作成するlinqクエリと同じです）。最終的に必要な場合は、結果のSeqからリストを作成することができます。リストは、すべてのフィルタリング、マッピングの最後に作成され、seqで作業を行い、最後のデータが準備完了になったらListに変換します。中間リストを作成しても問題は解決しません。