F # array_chunk für Sequence

Question

Ich habe einige Probleme eine Folge machen. Grundsätzlich muss ich eine Sequenz in eine Folge von Anordnungen zerhacken. Seq.windowed fast tut es, aber ich will keine doppelten Elemente.

kann ich bekommen, was ich will, indem sie alles in ein Array aus erster Lesung, aber ich würde eher eine Sequenz verwendet werden.

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. Die letzte wird kleiner sein, wenn die Sequenz nicht einmal von 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

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 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 und es soll effizienter als die Lösung sein, die Seq.skip verwendet. Auf der anderen Seite, trimmt es Eingabesequenz der Länge teilbar durch n. Wenn dieses Verhalten nicht akzeptabel ist, kann es durch einfache Modifikation festgelegt werden:

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 3

Diese Antwort wird wahrscheinlich begraben, aber hier ist mein nehmen auf 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 / nehmen Lösungen
• Seq.length muss nicht ein Vielfaches von n sein
• klein und leicht zu verstehen?

Nachteile:

• wahrscheinlich nicht so effizient wie Imperativ / wandelbar Schleifen

Answer 4

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, anders als Nehmen LINQ und Erweiterungsmethoden überspringen, erfordern, dass die Sequenz mindestens n Elemente enthält). Auch dies ist nicht so effizient wie explizit mit dem Enumerator wäre, aber es ist eleganter.

Answer 5

Korrigierte Version nehmen / überspringen Antwort, als Erweiterungsfunktion. Sollte für unebene Längen arbeiten. Keine Garantien für die Leistung aber ...

 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 hier )

Answer 6

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

jedoch lops dies die letzten (arr.Length% size) Elemente in der Anordnung ab. 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 7

Hier ist ein weiterer Ansatz mit einiger Musteranpassung - es eher wie * .iter aussieht, und ich habe es Listen spuckt anstatt Arrays, denn das ist, wie ich in der Regel wie meine Daten

.

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 8

Ich bin gefallen, diese Lösung besser. Es erzeugt eine neue Folge aus der bestehenden Sequenz (dh es ist nicht die ganze Sequenz zu durchqueren braucht ein Ergebnis zu erhalten - das ist entscheidend, wenn Sie so etwas wie Protokollverarbeitung tun, wo man nicht Dinge wie Länge nennen kann).

Ich landete einen Blog veröffentlicht mit mehr Details darüber, wie ich hierher gelangt sind.

module Seq =  

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

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

lassen grouped_by f s =     grouped_by_with_leftover_processing f YieldReversedLeftovers s

group_by_length_n n s lassen =     lassen grouping_function newValue acc =       lassen newList = newValue :: acc       // Wenn wir die richtige Länge haben, Rückkehr       // a Einige als der erste Wert. das wird       // durch die Sequenz nachgegeben werden.       wenn List.length acc = n - 1       Einige (List.rev newList) dann, []       // Wenn wir nicht die richtige Länge,       // Keine verwenden (so wird nichts nachgegeben)       sonst keine, 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 es: f = Seq [[1; 2; 3]; [4; 5; 6]; [7; 8; 9]; [10; 11; 12]; ...] >

Answer 9

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

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 10

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 die Position erinnert, so daß aufeinanderfolgende Einstellung / überspringen nicht optimal sein wird.

Answer 11

Hier @ KVB-Lösung mit der Seq.skip / nimm Beschränkungen festgelegt. 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 die gleiche Art und Weise machen Sie eine Sequenz aufbauen würden (so dass es leicht es neu zu schreiben, um eine Sequenz als Ausgabe zu erhalten)

Answer 13

zusammenfassend den oben Chunking oder Buffering oder Segmentieren eines seqence, Liste oder Array. Zwei Formen:

let rec chunk size xs = seq {
    yield Seq.take size xs
    yield! chunk size (Seq.skip size xs)
    }

oder

let chunk size = Seq.unfold (fun xs ->
    match Seq.isEmpty xs with
    | false -> Some(Seq.take size xs, Seq.skip size xs)
    | _ -> None
    )

Hinweis: Wenn Seq richtig wie ein Cursor funktioniert (wie ich eine lazy evaluation erwartet hätte sein), Seq.take würde die Position Seq.skip voran wäre nicht notwendig. Das ist jedoch nicht der Fall.