Java 8将n个大小的集合划分为m个未知大小的列表

Question

一般问题我不知道如何将排序列表划分为较小的排序列表，但不是以 Guava Lists.partition(list,size) 中的方式划分。 - 所以不是指定大小的较小列表，而是固定数量的类似大小的列表。

例如，有一个源列表:1,2,3,4，我希望有 3 个列表作为结果(3 是结果列表的固定数量)。我应该得到结果List<List<Long>> :ListOne:1，ListTwo:2，ListThree:3,4(请记住，保留排序)。当源列表小于目标列表的数量时，那么好吧，我可以获得更少数量的列表。因此，当源列表为 1,2 并且我想要 3 个列表时，算法应返回两个列表:List1 1，List2: 2。

源列表的大小未知，但有数十万个元素必须分为 10 个列表，因为这样就有 10 个线程准备对这些元素执行一些更复杂的操作。

下面的算法是完全错误的，源列表中有 14 个元素并传递 GRD_SIZE=10它返回 7 个包含 2 个元素的列表。它应该返回 GRD_SIZE=10类似大小的列表。也许我不应该使用 Guava Lists.partition 方法...但是如何完成这个任务？

List<List<Long>> partitions = partition(sourceList, GRD_SIZE);

public static <T> List<List<T>> partition(List<T> ascSortedItems, int size)
{
     int threadSize =  (int) Math.ceil(
         new BigDecimal(ascSortedItems.size()).divide(
             new BigDecimal(
                 ascSortedItems.size() >= size ? size : ascSortedItems.size()
             )
          ).doubleValue()
     );

     final AtomicInteger counter = new AtomicInteger(0);

     return ascSortedItems.stream()
         .collect(Collectors.groupingBy(it -> counter.getAndIncrement() / threadSize))
         .values()
         .stream()
         .collect(Collectors.toList());
}

Answer 1

首先，您不应该像您尝试的解决方案中那样使用可变计数器。一个规范的替代方案就像this answer ，在适应您的问题后，它看起来像:

return IntStream.range(0, (ascSortedItems.size()+threadSize-1)/threadSize)
    .mapToObj(i -> ascSortedItems
          .subList(i*threadSize, Math.min(ascSortedItems.size(), (i+1)*threadSize)))
    .collect(Collectors.toList());
}

threadSize的计算不需要那种奇怪的BigDecimal绕道。您可以将其计算为

int threadSize = Math.max(1, ascSortedItems.size()/size);

向下舍入或

int threadSize = Math.max(1, (ascSortedItems.size()+size-1)/size);

用于四舍五入。

但两者都不会按预期方式工作。继续您的示例，向下舍入将创建 14 个大小为 1 的列表，向上舍入将创建 7 个大小为 2 的列表。

真正的解决方案只能通过不首先计算批量大小来完成:

public static <T> List<List<T>> partition(List<T> ascSortedItems, int numLists) {
    if(numLists < 2) {
        if(numLists < 1) throw new IllegalArgumentException();
        return Collections.singletonList(ascSortedItems);
    }
    int listSize = ascSortedItems.size();
    if(listSize <= numLists) {
        return ascSortedItems.stream()
            .map(Collections::singletonList)
            .collect(Collectors.toList());
    }
    return IntStream.range(0, numLists)
        .mapToObj(i -> ascSortedItems.subList(i*listSize/numLists, (i+1)*listSize/numLists))
        .collect(Collectors.toList());
}

第一部分检查 numLists 参数的有效性并处理一个列表的简单特殊情况。

如果源列表小于请求的列表数量，中间部分处理返回较少列表的要求(否则，结果将始终具有请求的列表数量，可能包含空列表)。

最后一部分完成实际工作。正如您所看到的，初始的 IntStream.range(0, numLists) 总是会生成 numLists 元素，然后将这些元素映射到子列表，从而推迟舍入到可能的最新点。对于 [ 1, 2, 3, 4] 和三个请求列表的示例，它会生成

[1]
[2]
[3, 4]

对于 14 个元素并请求 10 个列表，它会生成

[1]
[2]
[3, 4]
[5]
[6, 7]
[8]
[9]
[10, 11]
[12]
[13, 14]

为了满足正好有十个列表的要求，不可避免地需要一些尺寸为一的列表和一些尺寸为二的列表。这是与第一个基于大小目标的解决方案的根本区别，其中最多一个列表的大小与其他列表的大小不同。