F # array_chunk für Sequence

Question

Ich habe einige Probleme eine Folge machen. Grundsätzlich muss ich eine Sequenz in eine Sequenz von Arrays zerlegen. Seq.windowed tut es fast, aber ich möchte keine doppelten Elemente.

kann ich bekommen, was ich will, indem man zuerst alles in ein Array zu lesen, aber ich würde eher eine Folge verwenden.

let array_chunk s (a:int[]) = 
    Array.init (a.Length/s) (fun i -> Array.sub a (i * s) s) 

someSequence |> Seq.to_array |> array_chunk 5 

Answer 1

Hier ist eine schöne zwingend notwendig, eine, die mit seq arbeiten werden und Arrays jeder Größe erzeugen. Der letzte wird kleiner sein, wenn die Folge nicht einmal um n ist.

let chunk n xs = seq { 
    let i = ref 0 
    let arr = ref <| Array.create n (Unchecked.defaultof<'a>) 
    for x in xs do 
     if !i = n then 
      yield !arr 
      arr := Array.create n (Unchecked.defaultof<'a>) 
      i := 0 
     (!arr).[!i] <- x 
     i := !i + 1 
    if !i <> 0 then 
     yield (!arr).[0..!i-1] } 

Answer 2

Wie wäre:

let rec chunks n sq = 
    if not (Seq.is_empty sq) then 
    seq { 
     yield Seq.take n sq |> Seq.to_array 
     yield! chunks n (Seq.skip n sq) 
    } 
    else 
    Seq.empty 

Beachten Sie, dass dies erfordert sq eine Reihe von Elementen zu haben, die durch n teilbar ist (weil Seq.take und Seq.skip, im Gegensatz zu LINQ 's Take und Erweiterung überspringen Methoden, erfordern, dass die Sequenz mindestens n Elemente enthält). Dies ist auch nicht so effizient, wie es explizit der Enumerator wäre, aber es ist eleganter.

Answer 3

Ich liebe Seq.take & Seq.skip Lösung. Es ist schön, einfach und sehr gut lesbar, aber ich würde so etwas wie folgt zu verwenden:

let chunks n (sequence: seq<_>) = 
    let fold_fce (i, s) value = 
     if i < n then (i+1, Seq.append s (Seq.singleton value)) 
       else ( 1, Seq.singleton value) 
    in sequence 
    |> Seq.scan (fold_fce) (0, Seq.empty) 
    |> Seq.filter (fun (i,_) -> i = n) 
    |> Seq.map (Seq.to_array << snd) 

Es ist nicht zwingend notwendig, Code ist, und es sollte effizienter als die Lösung sein, die Seq.skip verwendet. Auf der anderen Seite trimmt er die Eingabesequenz auf die Länge, die durch n teilbar ist. Wenn dieses Verhalten nicht akzeptabel ist es durch einfache Modifikation festgesetzt:

let chunks n (sequence: seq<_>) = 
    let fold_fce (i, s) value = 
     if i < n then (i+1, Seq.append s (Seq.singleton value)) 
       else ( 1, Seq.singleton value) 
    in sequence 
    |> Seq.map (Some) 
    |> fun s -> Seq.init_finite (n-1) (fun _ -> None) |> Seq.append s 
    |> Seq.scan (fold_fce) (0, Seq.empty) 
    |> Seq.filter (fun (i,_) -> i = n) 
    |> Seq.map (Seq.to_array << (Seq.choose (id)) << snd) 

Answer 4

Das ist schön und prägnant:

let chunk size (arr : 'a array) = 
    [| for a in 0 .. size .. arr.Length - size -> arr.[a..a + size - 1] |] 

Dies ist jedoch die letzte (arr.Length% Größe) Elemente in den lops aus Array. Sie können dieses Problem beheben, indem Sie die fehlenden Elemente greifen und mit Array.append:

let chunk2 size (arr : 'a array) = 
    let first = [| for a in 0 .. size .. arr.Length - size -> arr.[a..a + size - 1] |] 
    let numberOfMissingElements = arr.Length - (first.Length * size) 
    if numberOfMissingElements > 0 then 
     let last = [| arr.[arr.Length - numberOfMissingElements..] |] 
     Array.append first last 
    else first 

Answer 5

Hier sind ein weiterer Ansatz mit einiger Musteranpassung - es eher wie * .iter aussieht, und ich habe es Listen eher auszuspucken als Arrays , da ich meine Daten normalerweise so mag.

let sequence_in_lists_of_length_n_with_acc (s: seq<'a>) n acc = seq { 
use e = s.GetEnumerator() 
let rec next_with_acc acc = 
    match e.MoveNext(), acc with 
    | true, a when List.length a + 1 = n -> 
    yield (List.rev (e.Current :: a)) 
    next_with_acc [] 
    | true, _ -> next_with_acc (e.Current :: acc) 
    | false, _ -> 
    f(List.rev acc) 
() 
next_with_acc [] 

}

Answer 6

Ich bin gefallen, diese Lösung besser. Es erzeugt eine neue Sequenz aus der bestehenden Sequenz (das heißt, es muss nicht die gesamte Sequenz durchlaufen, um ein Ergebnis zu erhalten - das ist wichtig, wenn Sie etwas wie die Protokollverarbeitung tun, wo Sie Dinge wie Länge nicht nennen können).

Ich schrieb ein blog post mit mehr Details darüber, wie ich hierher kam.

module Seq = 

lassen grouped_by_with_leftover_processing f (f2: 'eine Liste -> Liste <' a> Option) (s: seq < 'a>) = rec grouped_by_with_acc (f lassen:' a -> ‚eine Liste - > 'eine Liste Option *' eine Liste) acc (dh: IEnumerator < ‚a>) = seq { wenn ie.MoveNext() dann nextvalue, Reste = f ie.Current nach wenn nextValue.IsSome dann lassen Ausbeute nextValue.Wert Ausbeute! grouped_by_with_acc f Reste dh sonst rem = f2 lassen nach wenn rems.IsSome dann rems.Value ergeben} seq { Ausbeute! grouped_by_with_acc f [] (s.GetEnumerator()) }

lassen YieldReversedLeftovers (f: ‚a list) = wenn f.IsEmpty dann keine sonst Einige (List.rev f)

let grouped_by fs = grouped_by_with_leftover_processing f YieldReversedLeftovers s

lassen group_by_length_n ns = grouping_function newValue acc lassen = lassen newList = newValue :: acc // Wenn wir die richtige Länge haben, kehren // a Einige als erster Wert. Das wird // durch die Sequenz ergeben. wenn List.length acc = n - 1 dann keine Einige (List.rev newList), [] // Wenn wir nicht die richtige Länge haben // Keine verwenden (so wird nichts nachgegeben werden) sonst newList,
grouped_by grouping_function s

Große Sequenzen sind kein Problem:

seq {für i in 1..1000000000 - > i} | > Seq.group_by_length_n 3 ;; val it: seq < int Liste > = seq [[1; 2; 3]; [4; 5; 6]; [7; 8; 9]; [10; 11; 12]; ...] >

Answer 7

Nizza Version von Prinzessin wurde behoben Schwanz zu bekommen und umgewandelt in Seq

let array_chunk size (arr : 'a array) = 
    let maxl = arr.Length - 1 
    seq { for a in 0 .. size .. maxl -> arr.[a .. min (a + size - 1) maxl ] } 

Answer 8

Korrigierte Version von Take/überspringen Antwort, als Erweiterungsfunktion. Sollte für ungleiche Längen arbeiten. obwohl keine Garantien für die Leistung ...

module Seq = 
    let rec chunks n (s:#seq<_>) = 
     seq { 
       if Seq.length s <= n then 
        yield s 
       else 
        yield Seq.take n s 
        yield! chunks n (Seq.skip n s)   
      } 

(-Code aus meiner Antwort genommen here)

Answer 9

Wie wäre es dieses:

let grouped n = 
    Seq.unfold(fun s -> if not (Seq.isEmpty s) then 
          Some (Seq.take n s, Seq.skip n s) 
         else None) 

Es ist in der gleichen Ader als kvb Antwort.

Ich erinnere mich irgendwie (Link?), Dass eine Sequenz nicht an die Position erinnert, so dass aufeinanderfolgende Take/Skip nicht optimal sein wird.

Answer 10

Diese Antwort wird wahrscheinlich begraben, aber mein nehmen hier ist das Problem:

let chunk n xs = 
    xs 
    |> Seq.mapi(fun i x -> i/n, x) 
    |> Seq.groupBy fst 
    |> Seq.map (fun (_, g) -> Seq.map snd g) 

Vorteile:

• Verwendet nur seq, keine Arrays
• O (n) Laufzeit. Nicht O (n^2) wie Seq.skip/nimm Lösungen
• Seq.Länge muss nicht ein Vielfaches von n sein
• klein und leicht zu verstehen?

Nachteile:

• wahrscheinlich nicht so effizient wie Imperativ/wandelbar Schleifen

Answer 11

Hier Lösung des @ kvb mit der Seq.skip/fixed nehmen Einschränkungen. Es ist klein, elegant und O (n).

let eSkip n s = System.Linq.Enumerable.Skip(s, n) 

let rec seq_chunks n sq = 
    if (Seq.isEmpty sq) 
    then Seq.empty 
    else seq { 
     yield Seq.truncate n sq 
     yield! seq_chunks n (eSkip n sq) 
} 

Answer 12

Hier ist meine Version einen Array als Eingabe und Ausgabe unter:

let chunk chunkNumber (array : _ array) = 
    let chunkSize = array.Length/chunkNumber 
    let mutable startIndex = 0 
    [| 
     let n1 = array.Length % chunkNumber 
     for i = 1 to n1 do 
      yield Array.sub array startIndex (chunkSize+1) 
      startIndex <- startIndex + chunkSize+1 

     let n2 = chunkNumber - n1 
     for i = 1 to n2 do 
      yield Array.sub array startIndex chunkSize 
      startIndex <- startIndex + chunkSize 
    |] 

Die Funktion versucht, Stücke von ähnlicher Größe (anstatt ich einen sehr kleinen letzten Brocken) und baut die Ausgabe des machen Auf dieselbe Weise würden Sie eine Sequenz erstellen (was es einfach macht, sie neu zu schreiben, um eine Sequenz als Ausgabe zu erhalten)