2016-07-15 10 views
1

私はF番号:要素のシーケンスを繰り返しによってグループ化

[("a", 1), ("a", 2), ("a", 111), ("b", 3), ("bb", 1), ("bb", -1), ...] 

のようなペア(キー、値)の配列を有し、同様にシーケンスに変換するための最も効果的な方法は何ですか

[("a", [1,2,111]), ("b", [3]), ("bb", [1,-1])] 

または類似?

シーケンスは、プロパティを以下ました:それは本当に大きいです(> 2GB)

をこれはSeq.groupByは本当に効果がないと間違った行い、それを行うには、他の方法がありますか?

PS:このシーケンス:

[("a", 1), ("a", 2), ("a", 111), ("bb", 1), ("bb", -1), ("a", 5), ("a", 6), ...] 

[("a", [1,2,111]), ("bb", [1,-1]), ("a", [5,6]), ...] 

として変換されなければならない -

編集#1:固定間違ったサンプル

編集#2:シーケンスであります大きな、怠惰な(または最速の)ソリューションが好ましい

+2

seq.groupbyはどのように間違っていますか? –

+1

@JohnPalmer:groupByは[内部的に辞書](https://github.com/fsharp/fsharp/blob/37a100b7caafde0f4df5a1924c9f65f4a18277a8/src/fsharp/FSharp.Core/seq.fs#L1458)を使用しています。 OPは避けたい彼は 'uniq'に似た振る舞いをしているようだ。 –

+0

@AntonSchwaighofer - groupbyが間違っている理由がたくさんある - 彼の状況に何が適用されるのかをOPに伝えようとしていた - –

答えて

3

オプションを怠惰な結果にしたい場合は、変更可能な状態を維持しないでエレガントな方法がないと思います。ここに突然変異を持つ比較的単純なものがあります。あなたが見た最後のキーのストアを維持し、それに対応するすべての値:

let s = [("a", 1); ("a", 2); ("a", 111); ("bb", 1); ("bb", -1); ("a", 5); ("a", 6)] 
let s2 = 
    [ 
     let mutable prevKey = None 
     let mutable values = System.Collections.Generic.List<_>() 
     let init key value = 
      prevKey <- Some key 
      values.Clear() 
      values.Add value 
     for (key, value) in s do 
      match prevKey with 
      | None -> init key value 
      | Some k when k = key -> values.Add value 
      | Some k -> 
       yield (k, List.ofSeq values) 
       init key value 
     match prevKey with 
     | Some k -> yield (k, List.ofSeq values) 
     | _ ->() 
    ] 

これが与える:遅延評価については

val s2 : (string * int list) list = 
    [("a", [1; 2; 111]); ("bb", [1; -1]); ("a", [5; 6])] 

を、seq { ... }

+0

この種の解決策では、レイジー評価ではないという問題があります。シーケンスが最後の要素になるまでシーケンスを読み続けることになります。あなたのバージョン、または私の同様の解決策は*遅い* Seq.groupBy(ofcは間違った答えを与えますが...) – Darkkey

+0

またこのバージョンは間違いがあります。正しい結果は次のようになります: [( "a" [1; 2; 111])。 (「bb」、「1; -1」)。 ( "a"、[5; 6])] – Darkkey

+1

バグが修正されました。 '[...]'を 'seq {...} 'に置き換えてください。 –

2

[ ... ]を置き換えます可変状態のない単純な再帰的アプローチ。ここで

let rec chunk inseq (accumelem,accumlist) = 
    match inseq with 
    |(a,b)::c -> 
     match accumelem with 
     |Some(t) -> if t=a then chunk c (accumelem,b::accumlist) else (t,accumlist)::(chunk c (Some(a),b::[])) 
     |None -> chunk c (Some a,b::[]) 
    |[] ->   
     match accumelem with 
     |Some(t) -> (t,accumlist)::[] 
     |None -> [] 


chunk [("a", 1); ("a", 2); ("a", 111); ("bb", 1); ("bb", -1); ("a", 5);("a", 6)] (None,[]) 

val it : (string * int list) list = 
    [("a", [111; 2; 1]); ("bb", [-1; 1]); ("a", [6; 5])] 
2

が再帰的なソリューションです:

let test = [("a", 1); ("a", 2); ("a", 111); ("bb", 1); ("bb", -1); ("a", 5); ("a", 6)] 

let groupByAdjacentElements alist = 
    let rec group a groupAcc prevElement adjacentAcc = 
     match a with 
     | [] -> match adjacentAcc with 
       | [] -> groupAcc 
       | _ -> (prevElement, List.rev adjacentAcc)::groupAcc 
     | (b, c)::tail -> if b = prevElement then 
          group tail groupAcc prevElement (c::adjacentAcc) 
          else 
          group tail ((prevElement, List.rev adjacentAcc)::groupAcc) b [c] 

    group alist [] (fst alist.Head) [] 
    |> List.rev 

let b = groupByAdjacentElements test 

それを返します:[("a", [1; 2; 111]); ("bb", [1; -1]); ("a", [5; 6])]

あなたは遅延評価をしたい場合、あなたはLazyList

EDITをしようとして検討する必要があります。ここではLazyListを比較するスクリプトがありますExtCoreから受け入れられた解決策へ。それは大きなテキストファイルを生成し、変換を求めます。 LazyListは逆の順序で返されることに注意してください:私はサイズの周り300メガバイトのファイルを使用している場合

open System.Diagnostics 
open System.IO 
open ExtCore 

let fileName = "Test.txt" 
let outFile = new StreamWriter(fileName) 
for i in [1..20000*300] do 
    outFile.WriteLine("a,1") 
    outFile.WriteLine("a,2") 
    outFile.WriteLine("a,111") 
    outFile.WriteLine("bb,1") 
    outFile.WriteLine("bb,-1") 
    outFile.WriteLine("a,5") 
    outFile.WriteLine("a,6") 
    outFile.WriteLine("c,8") 
outFile.Close() 

printfn "Finished Writing to File" 

let data = System.IO.File.ReadLines(fileName) 
      |> Seq.map (fun i -> let parts = i.Split(',') 
           (parts.[0], parts.[1])) 
printfn "Finished Reading File" 

let s2 data = 
    [ 
     let mutable prevKey = None 
     let mutable values = System.Collections.Generic.List<_>() 
     let init key value = 
      prevKey <- Some key 
      values.Clear() 
      values.Add value 
     for (key, value) in data do 
      match prevKey with 
      | None -> init key value 
      | Some k when k = key -> values.Add value 
      | Some k -> 
       yield (k, List.ofSeq values) 
       init key value 
     match prevKey with 
     | Some key -> yield (key, List.ofSeq values) 
     | _ ->() 
    ] 

let groupByAdjacentElements aseq = 
    let alist = LazyList.ofSeq aseq 
    let rec group alist groupAcc prevElement adjacentAcc = 
     match alist with 
     | Cons((b, c), tail) -> 
      if b = prevElement then 
       group tail groupAcc prevElement (c::adjacentAcc) 
      else 
       group tail (LazyList.consDelayed (prevElement, List.rev adjacentAcc) (fun() -> groupAcc)) b [c] 
     | Nil -> 
      match adjacentAcc with 
      | [] -> groupAcc 
      | _ -> LazyList.consDelayed (prevElement, List.rev adjacentAcc) (fun() -> groupAcc) 


    group alist LazyList.empty (fst (alist.Head())) [] 

let groupByAdjacentElementsList aseq = 
    let alist = aseq |> Seq.toList 
    let rec group a groupAcc prevElement adjacentAcc = 
     match a with 
     | [] -> match adjacentAcc with 
       | [] -> groupAcc 
       | _ -> (prevElement, List.rev adjacentAcc)::groupAcc 
     | (b, c)::tail -> if b = prevElement then 
          group tail groupAcc prevElement (c::adjacentAcc) 
          else 
          group tail ((prevElement, List.rev adjacentAcc)::groupAcc) b [c] 

    group alist [] (fst alist.Head) [] 
    |> List.rev 

[<EntryPoint>] 
let main argv = 
    let stopwatch = new Stopwatch() 
    stopwatch.Start() 
    let b = s2 data 
    printfn "The result is: %A" b 
    stopwatch.Stop() 
    printfn "It took %A ms." stopwatch.ElapsedMilliseconds 
    System.GC.WaitForFullGCComplete() |> ignore 
    stopwatch.Reset() 
    stopwatch.Start() 
    let b = groupByAdjacentElements data 
    printfn "The result is: %A" b 
    stopwatch.Stop() 
    printfn "It took %A ms." stopwatch.ElapsedMilliseconds 
    System.GC.WaitForFullGCComplete() |> ignore 
    stopwatch.Reset() 
    stopwatch.Start() 
    let b = groupByAdjacentElementsList data 
    printfn "The result is: %A" b 
    stopwatch.Stop() 
    printfn "It took %A ms." stopwatch.ElapsedMilliseconds 
    0 

LazyListseqソリューションよりもわずかに遅い(94Sに83S)でした。 LazyListには、シーケンスソリューションとは異なり、反復処理がキャッシュされるという大きな利点があります。 List.revを実行していても、通常のリストの解法は両方よりも速くなりました(73年頃はありませんでした)。

0

バインディングを変更せずに隣接するキーでグループ化することもできます。Seq.scanでは、熱心なチャンクでレイジーシーケンスを生成することができます。これは、特別なケースの1つ、シーケンスの最初の要素をすでに提供しています。オプションとして入力シーケンスをラップすることによって、Noneを処理して、もう一方を処理することができます。その後、中間結果をスキップしてSeq.chooseで状態を取り除きます。最初の引数としてキー投影関数を取る

最大の汎用性のために、私はSeq.groupByと同様の署名を示唆したいは、

f:('T -> 'Key) -> xs:seq<'T> -> seq<'Key * 'T list> when 'Key : equality 

let chunkBy (f : 'T-> 'Key) xs = 
    // Determine key and wrap in option 
    seq{for x in xs -> Some(f x, x) 
     // Indicates end of sequence 
     yield None } 
    |> Seq.scan (fun (_, acc, previous) current -> 
     match previous, current with 
     | Some(pKey, _), Some(key, value) when pKey = key -> 
      // No intermediate result, but add to accumulator 
      None, value::acc, current 
     | _ -> 
      // New state is 3-tuple of previous key and completed chunk, 
      // accumulator from current element, and new previous element 
      Option.map (fun (k, _) -> k, List.rev acc) previous, 
      Option.map snd current |> Option.toList, current) 
     (None, [], None) 
    |> Seq.choose (fun (result, _, _) -> result) 

これは、結果投影機能も提供することによってOPの要件に採用することができます。

let chunkBy2 (f : 'T-> 'Key) (g : 'T->'Result) = 
    chunkBy f >> Seq.map (fun (k, gs) -> k, List.map g gs) 
// val chunkBy2 : 
// f:('T -> 'Key) -> g:('T -> 'Result) -> (seq<'T> -> seq<'Key * 'Result list>) 
//  when 'Key : equality 

["a", 1; "a", 2; "a", 111; "b", 3; "bb", 1; "bb", -1] 
|> chunkBy2 fst snd 
// val it : seq<string * int list> = 
// seq [("a", [1; 2; 111]); ("b", [3]); ("bb", [1; -1])] 

Seq.initInfinite (fun x -> 
    if (x/2) % 2 = 0 then "a", x else "b", x) 
|> chunkBy2 fst snd 
|> Seq.skip 50000 
// val it : seq<string * int list> = 
// seq 
//  [("a", [100000; 100001]); ("b", [100002; 100003]); ("a", [100004; 100005]); 
//  ("b", [100006; 100007]); ...] 
関連する問題