分组后对列表进行排序

Question

我想知道流（或收集器）中是否已经实现了将列表排序为值的功能。例如。以下代码都生成按性别分组的人员列表，并按年龄排序。第一个解决方案有一些开销排序（并且看起来有点邋遢）。第二种解决方案需要对每个人进行两次检查，但效果很好。

首先排序，然后分组到一个流中：

Map<Gender, List<Person>> sortedListsByGender = (List<Person>) roster
        .stream()
        .sorted(Person::compareByAge)
        .collect(Collectors.groupingBy(Person::getGender));

首先分组，然后对每个值进行排序：

Map<Gender, List<Person>> sortedListsByGender = (List<Person>) roster
        .stream()
        .collect(Collectors.groupingBy(Person::getGender));
sortedListsByGender.values()
        .forEach(list -> Collections.sort(list, Person::compareByAge));

我只是想知道，是否已经实现了某些功能，可以一次性完成此操作，例如

groupingBySorted

。

Answer 1

当在

sorted(comparator)

操作之前在流上使用

collect

时，流必须缓冲整个流内容才能对其进行排序，并且与对较小列表进行排序相比，排序可能涉及该缓冲区内更多的数据移动之后的小组。因此，尽管如果启用并行处理，实现将利用多个核心，但性能不如对各个组进行排序。

但请注意，使用

sortedListsByGender.values().forEach(…)

不是可并行操作，即使使用

sortedListsByGender.values().parallelStream().forEach(…)

也只允许并行处理组，而每个排序操作仍然是顺序的。

在收集器中执行排序操作时，如下

static <T> Collector<T,?,List<T>> toSortedList(Comparator<? super T> c) {
    return Collectors.collectingAndThen(
        Collectors.toCollection(ArrayList::new), l->{ l.sort(c); return l; } );
}

 

Map<Gender, List<Person>> sortedListsByGender = roster.stream()
    .collect(Collectors.groupingBy(Person::getGender, toSortedList(Person::compareByAge)));

排序操作的行为相同（感谢 Tagir Valeev 纠正我），但您可以轻松检查插入时排序策略的执行情况。只需将收集器实现更改为：

static <T> Collector<T,?,List<T>> toSortedList(Comparator<? super T> c) {
    return Collectors.collectingAndThen(
        Collectors.toCollection(()->new TreeSet<>(c)), ArrayList::new);
}

为了完整起见，如果您想要一个首先插入排序到

ArrayList

以避免最终复制步骤的收集器，您可以使用更详细的收集器，如下所示：

static <T> Collector<T,?,List<T>> toSortedList(Comparator<? super T> c) {
    return Collector.of(ArrayList::new,
        (l,t) -> {
            int ix=Collections.binarySearch(l, t, c);
            l.add(ix<0? ~ix: ix, t);
        },
        (list1,list2) -> {
            final int s1=list1.size();
            if(list1.isEmpty()) return list2;
            if(!list2.isEmpty()) {
                list1.addAll(list2);
                if(c.compare(list1.get(s1-1), list2.get(0))>0)
                    list1.sort(c);
            }
            return list1;
        });
}

对于顺序使用来说是高效的，但是它的合并功能并不是最优的。底层排序算法将受益于预排序范围，但必须首先找到这些范围，尽管我们的合并函数实际上知道这些范围。不幸的是，JRE 中没有公共 API 允许我们有效地利用这些信息（高效；我们可以将

subList

传递给

binarySearch

，但为

list2

的每个元素创建一个新的子列表可能会变得过于昂贵） 。如果我们想进一步提高并行执行的性能，我们必须重新实现排序算法的合并部分：

static <T> Collector<T,?,List<T>> toSortedList(Comparator<? super T> c) {
    return Collector.of(ArrayList::new,
        (l,t) -> l.add(insertPos(l, 0, l.size(), t, c), t),
        (list1,list2) -> merge(list1, list2, c));
}
static <T> List<T> merge(List<T> list1, List<T> list2, Comparator<? super T> c) {
    if(list1.isEmpty()) return list2;
    for(int ix1=0, ix2=0, num1=list1.size(), num2=list2.size(); ix2<num2; ix2++, num1++) {
        final T element = list2.get(ix2);
        ix1=insertPos(list1, ix1, num1, element, c);
        list1.add(ix1, element);
        if(ix1==num1) {
            while(++ix2<num2) list1.add(list2.get(ix2));
            return list1;
        }
    }
    return list1;
}
static <T> int insertPos(
    List<? extends T> list, int low, int high, T t, Comparator<? super T> c) {
    high--;
    while(low <= high) {
        int mid = (low+high)>>>1, cmp = c.compare(list.get(mid), t);
        if(cmp < 0) low = mid + 1;
        else if(cmp > 0) high = mid - 1;
        else {
            mid++;
            while(mid<=high && c.compare(list.get(mid), t)==0) mid++;
            return mid;
        }
    }
    return low;
}

请注意，与简单的基于

binarySearch

的插入不同，最后一个解决方案是一个稳定的排序实现，即在您的情况下，具有相同年龄的

Person

和

Gender

不会改变它们的相对顺序，如果源流具有定义的遭遇顺序。

Answer 2

是的，我们可以groupBy，然后在一行中排序。下面的代码行首先按性别分组，然后按年龄排序[假设 getGender() 和 getAge() 作为 getter]

roster.stream().sorted(Comparator.comparing(Person::getGender).thenComparing(Person::getAge)).collect(Collectors.toList()))