如何使用给定的组大小对列表进行分区? [英] How to partition a list with a given group size?

问题描述

我正在寻找对列表(或 seq)进行分区的最佳方法，以便组具有给定的大小.例如.假设我想以大小 2 分组(尽管这可以是任何其他数字):

I'm looking for the best way to partition a list (or seq) so that groups have a given size. for ex. let's say I want to group with size 2 (this could be any other number though):

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 的明显方法是将位置添加到输入列表中的每个元组，使其成为

The obvious way to implement partitionBySize would be by adding the position to every tuple in the input list so that it becomes

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

然后将 GroupBy 与

and then use GroupBy with

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

然而，这个解决方案对我来说看起来并不优雅.有没有更好的方法来实现这个功能(也许是内置函数)?

However this solution doesn't look very elegant to me. Is there a better way to implement this function (maybe with a built-in function)?

推荐答案

这是一个遍历列表一次的尾递归函数.

Here's a tail-recursive function that traverses the list once.

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

我喜欢 Tomas 方法的优雅，但我使用包含 1000 万个元素的输入列表对我们的两个函数进行了基准测试.这一个计时为 9 秒，而他的计时为 22 秒.当然，正如他所承认的，最有效的方法可能是数组/循环.

I like the elegance of Tomas' approach, but I benchmarked both our functions using an input list of 10 million elements. This one clocked in at 9 secs vs 22 for his. Of course, as he admitted, the most efficient method would probably involve arrays/loops.

这篇关于如何使用给定的组大小对列表进行分区?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！