F# массив_частиц для последовательности

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 и генерировать массивы любого размера.Последний будет меньше, если последовательность не равна даже 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 2

Я люблю 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 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.длина не обязательно должна быть кратна n
• маленький и понятный?

Минусы:

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

Answer 4

Как насчет:

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 5

Исправленная версия take / skip answer в качестве дополнительной функции.Должно подойти для неравномерной длины.Однако никаких гарантий производительности нет...

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

Вот еще один подход с некоторым сопоставлением шаблонов - он больше похож на *.iter , и у меня он выдает списки, а не массивы, поскольку именно так мне обычно нравятся мои данные.

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

Мне это решение нравится больше.Он генерирует новую последовательность из существующей последовательности (это означает, что ему не нужно проходить всю последовательность, чтобы получить результат - это важно, если вы делаете что-то вроде обработки журнала, где вы не можете вызывать такие вещи, как Длина).

В итоге я написал запись в блоге с более подробной информацией о том, как я сюда попал.

module Seq =  

пусть grouped_by_with_leftover_processing f (f2:'список -> список<'a> опция) (ы:продолжение<'a>)= пусть rec grouped_by_with_acc (f:'a -> 'список -> 'опция списка * 'список) в соответствии (ie:I - нумератор<'a>) = seq { если ie.MoveNext() тогда пусть NextValue, остатки = f ie.Текущий счет если значение NextValue.Является некоторым, то выдайте значение NextValue.Значение выдайте!grouped_by_with_acc f остатки, т.е. else пусть rems = f2 acc если rems.является некоторым, то выдайте rems.Значение } seq { выдайте!grouped_by_with_acc f [] (s.GetEnumerator()) }

пусть yielddreversedleftovers (f:'список) = если f.пусто тогда Нет еще какой-нибудь (List.rev f)

пусть grouped_by f s = grouped_by_with_leftover_processing f дает обратные остатки s

пусть group_by_length_n n s = пусть grouping_function новое значение acc = пусть newList = новое значение ::acc // Если у нас есть правильная длина, верните // a Some в качестве первого значения.Это будет // получено последовательностью.если List.length acc = n - 1 тогда Some (List.rev newList), [] // Если у нас нет нужной длины, // используйте None (так что ничего не будет выдано) else Нет, новый список
grouped_by группировка_функции s

Большие последовательности не являются проблемой:

seq { для i в 1..1000000000 -> i} |> Seq.group_by_length_n 3;;вал это :продолжение<int list=""> = продолжение [[1;2;3];[4;5;6];[7;8;9];[10;11;12];...] >

Answer 9

Хорошая версия от Princess была исправлена, чтобы получить tail и преобразована в 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 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.

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

Answer 11

Вот решение @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 12

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

  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 13

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

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 не был бы необходим.Однако это не тот случай.