F #: группировка повторяющихся последовательностей элементов

Question

У меня есть последовательность пар (ключ, значение), как

[("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: Последовательность большой, так ленивый (или самый быстрый) раствор является предпочтительным

Answer 1

Если вы хотите получить ленивые результаты, я не думаю, что есть элегантный способ, не поддерживая изменчивое состояние. Вот относительно прямолинейный с мутацией. Вы утверждаете запас последнего ключа, который вы видели, и все значения, которые соответствуют тому, что:

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 { ... }

Answer 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])] 

Answer 3

Вот рекурсивное решение:

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 возвращается в обратном порядке:

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 

я при использовании файлов вокруг 300MB в размерах, LazyList был немного медленнее (83s до 94S), чем seq раствора. При этом LazyList имеет главное преимущество в том, что итерация по нему кэшируется, в отличие от решения последовательности. Обычное решение списка было быстрее, чем даже при выполнении List.rev (без него было около 73 секунд).

Answer 4

Группировка смежными ключами также может выполняться без измененных привязок.С Seq.scan можно генерировать ленивую последовательность с нетерпеливым куском. Он уже предусматривает один из особых случаев - первый элемент последовательности; путем упаковки входной последовательности в качестве параметров, за которыми следует 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) 

Это может быть адаптировано к требованиям ОП, предоставляя также функцию проекции результата.

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]); ...]