Блог

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

 let xs = [(a,b,c); (a,b,d); (y,z,y); (w,y,z); (n,y,z)]
let grouped = partitionBySize 2 input
// => [[(a,b,c);(a,b,d)]; [(y,z,y);(w,y,z)]; [(n,y,z)]]
  

Очевидным способом реализации partitionBySize было бы добавление позиции к каждому кортежу во входном списке, чтобы он стал

 [(0,a,b,c), (1,a,b,d), (2,y,z,y), (3,w,y,z), (4,n,y,z)]
  

а затем использовать GroupBy с

 xs |> Seq.ofList |> Seq.GroupBy (function | (i,_,_,_) -> i - (i % n))
  

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

Похоже, это повторяющийся шаблон, который не фиксируется ни одной функцией в библиотеке ядра F #. При решении аналогичных задач ранее я определил функцию Seq.groupWhen (см. фрагменты F #), которая превращает последовательность в группы. Новая группа запускается, когда выполняется предикат.

Вы могли бы решить проблему, используя Seq.groupWhen аналогично Seq.group (запустив новую группу с четным индексом). В отличие от Seq.group , это эффективно, потому что Seq.groupWhen повторяет входную последовательность только один раз:

 [3;3;2;4;1;2;8] 
|> Seq.mapi (fun i v -> i, v) // Add indices to the values (as first tuple element)
|> Seq.groupWhen (fun (i, v) -> i%2 = 0) // Start new group after every 2nd element
|> Seq.map (Seq.map snd) // Remove indices from the values
  

Реализовать функцию напрямую, используя рекурсию, вероятно, проще — решение от Джона делает именно то, что вам нужно, — но если вы хотели увидеть более общий подход, то Seq.groupWhen это может быть интересно.

List.chunkBySize (главный совет: Скотт Влашин) теперь доступен и делает именно то, о чем вы говорите. Похоже, что это новое с F # 4.0.

 let grouped = [1..10] |> List.chunkBySize 3
// val grouped : int list list = 
//   [[1; 2; 3]; [4; 5; 6]; [7; 8; 9]; [10]]
  

Seq.chunkBySize и Array.chunkBySize также теперь доступны.

Вот хвостовая рекурсивная функция, которая проходит по списку один раз.

 let chunksOf n items =
  let rec loop i acc items = 
    seq {
      match i, items, acc with
      //exit if chunk size is zero or input list is empty
      | _, [], [] | 0, _, [] -> ()
      //counter=0 so yield group and continue looping
      | 0, _, _::_ -> yield List.rev acc; yield! loop n [] items 
      //decrement counter, add head to group, and loop through tail
      | _, h::t, _ -> yield! loop (i-1) (h::acc) t
      //reached the end of input list, yield accumulated elements
      //handles items.Length % n <> 0
      | _, [], _ -> yield List.rev acc
    }
  loop n [] items
  

Использование

 [1; 2; 3; 4; 5]
|> chunksOf 2 
|> Seq.toList //[[1; 2]; [3; 4]; [5]]
  

Мне нравится элегантность подхода Томаса, но я провел сравнительный анализ обеих наших функций, используя входной список из 10 миллионов элементов. У этого тактовая частота составила 9 секунд против 22 у его. Конечно, как он признал, наиболее эффективным методом, вероятно, были бы массивы / циклы.

Как насчет рекурсивного подхода? — требуется только один проход

 let rec partitionBySize length inp dummy = 
    match inp with
    |h::t ->
        if dummy |> List.length < length then
            partitionBySize length t (h::dummy)
        else dummy::(partitionBySize length t (h::[]))
    |[] -> dummy::[]
  

Затем вызовите его с помощью partitionBySize 2 xs []

 let partitionBySize size xs =
  let sq = ref (seq xs)
  seq {
    while (Seq.length !sq >= size) do
      yield Seq.take size !sq
      sq := Seq.skip size !sq
    if not (Seq.isEmpty !sq) then yield !sq
  }
  // result to list, if you want
  |> Seq.map (Seq.toList)
  |> Seq.toList
  

Обновить

 let partitionBySize size (sq:seq<_>) =
  seq {
    let e = sq.GetEnumerator()
    let empty = ref true;
    while !empty do
      yield seq { for i = 1 to size do
                    empty := e.MoveNext()
                    if !empty then yield e.Current
            }
  }
  

версия фрагмента массива:

 let partitionBySize size xs =
  let xa = Array.ofList xs
  let len = xa.Length
  [
    for i in 0..size..(len-1) do
      yield ( if i   size >= len then xa.[i..] else xa.[i..(i size-1)] ) |> Array.toList 
  ]
  

Ну, я опоздал на вечеринку. Приведенный ниже код представляет собой хвостовую рекурсивную версию, использующую функции высокого порядка на List :

 let partitionBySize size xs =
    let i = size - (List.length xs - 1) % size
    let xss, _, _ =
        List.foldBack( fun x (acc, ls, j) -> 
                                          if j = size then ((x::ls)::acc, [], 1) 
                                          else (acc, x::ls, j 1)
                       ) xs ([], [], i)
    xss
  

Я выполнил тот же тест, что и Дэниел. Эта функция эффективна, хотя она в 2 раза быстрее, чем его подход на моей машине. Я также сравнил его с версией массива / цикла, они сопоставимы с точки зрения производительности.

Более того, в отличие от ответа Джона, эта версия сохраняет порядок элементов во внутренних списках.