F # array_chunk для последовательности

Question

У меня возникли проблемы при создании последовательности. В основном мне нужно разделить последовательность на последовательность массивов. Seq.windowed почти делает это, но я не хочу дублировать элементы.

Я могу получить то, что хочу, сначала прочитав все в массив, но лучше использовать последовательность.

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

Я люблю Seq.take & Seq.skip решение. Это красиво, просто и очень читабельно, но я бы использовал что-то вроде этого:

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 )

Это не обязательный код, и он должен быть более эффективным, чем решение, использующее Seq.skip. С другой стороны, он обрезает входную последовательность до длины, кратной n. Если это поведение неприемлемо, его можно исправить простой модификацией:

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 2

Вот хороший императив, который будет работать с seq и генерировать массивы любого размера. Последний будет меньше, если последовательность даже не равна n.

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 3

Этот ответ, вероятно, будет похоронен, но вот мой взгляд на проблему:

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

Плюсы:

• Использует только seq, без массивов
• O (n) время выполнения. Не O (n ^ 2), как Seq.skip / take solutions
• Seq.length не должен быть кратным n
• маленький и простой для понимания?

Минусы:

• вероятно, не так эффективен, как императивные / изменяемые циклы

Answer 4

Исправленная версия ответа на вопрос «принять / пропустить» в качестве функции расширения. Должен работать на неровной длины. Хотя нет никаких гарантий для производительности ...

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

(Код взят из моего ответа здесь )

Answer 5

Как насчет:

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

Обратите внимание, что для этого требуется, чтобы sq имел количество элементов, которые делятся поровну на n (потому что Seq.take и Seq.skip, в отличие от методов расширения LINQ Take и Skip, требуют, чтобы последовательность содержала как минимум n элементов). Кроме того, это не так эффективно, как было бы явно использовать перечислитель, но оно более элегантно.

Answer 6

Это красиво и лаконично:

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

Однако это обрезает последние (arr.Length% size) элементы в массиве. Вы можете исправить это, взяв недостающие элементы и используя 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

Обобщая вышеупомянутые Чанкинг или Буферизация или Сегментирование последовательности, списка или массива. Две формы:

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

или

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

Примечание: если бы Seq функционировал правильно, как курсор (как я и ожидал, это ленивая оценка), Seq.take продвинул бы позицию, в которой Seq.skip не был бы необходим. Однако это не так.

Answer 8

Вот моя версия, принимающая массив в качестве ввода и вывода:

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

Функция пытается создать чанки одинакового размера (вместо получения очень маленького последнего чанка) и создает выходные данные так же, как вы строите последовательность (что упрощает ее переписывание для получения последовательности в качестве выходной)

Answer 9

Вот решение @ kvb с фиксированными ограничениями Seq.skip / take. Он маленький, элегантный и 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 10

Как насчет этого:

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

Это в том же духе, что и ответ kvb.

Я как-то помню (ссылка?), Что последовательность не запоминает позицию, так что последующий захват / пропуск не будет оптимальным.