当前位置: 首页 > 知识库问答 >
问题:

分组后对列表进行排序

史磊
2023-03-14

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

首先排序,然后在一个流中分组:

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

我只是想知道,是否已经实现了一些东西,可以在一次运行中完成,比如group pingBySorted

共有1个答案

杨飞飙
2023-03-14

当在收集操作之前对流使用排序(比较器)时,流必须缓冲整个流内容才能对其进行排序,与排序相比,排序可能涉及该缓冲区内更多的数据移动之后小组的较小列表。因此,性能不如排序单个组,尽管如果启用并行处理,实现将使用多个内核。

但请注意,使用sortedListByGender。值()。forEach(…)不是一个可并行操作,甚至使用sortedListsByGender。值()。并行流()。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允许我们有效地利用这些信息(我们可以将子列表s传递给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插入不同,最后一种解决方案是一种稳定的排序实现,即在您的情况下,如果源流具有定义的相遇顺序,则年龄和性别相同的Persons不会更改其相对顺序。

 类似资料:
  • 问题内容: 我想知道,流(或收集器)中是否已经有一个已实现的功能,已将列表作为值进行了排序。例如,以下代码均产生按年龄分组的按性别分组的人员清单。第一个解决方案具有一些开销排序(看起来有些sc琐)。第二种解决方案需要对每个人进行两次检查,但是必须做到很好。 首先排序,然后分组为一个流: 首先分组,然后对每个值进行排序: 我只是想知道,是否已经实现了某项功能,该功能可以一次运行,例如。 问题答案:

  • 我有一个过程对象列表,如下所示 我的程序课就像 我想基于以下条件对对象进行排序和分组。 应根据过程名称对所有过程进行分组。 过程必须按过程日期降序排列。[日期列表中的第一个元素,即 分组在一起的相同过程应按日期降序排列。 最终结果必须是, 我能够使用比较器和旧的Java代码实现这一点。是否可以使用java8流、收集器和分组来实现相同的功能?

  • 问题内容: 我具有以下数据结构(列表列表) 我希望能够 使用函数对列表重新排序,以便我可以按列表中的每个项目分组。例如,我希望能够按第二列分组(以便所有21列在一起) 使用函数仅显示每个内部列表中的某些值。例如,我想减少此列表,使其仅包含“ 2somename”的第四个字段值 所以列表看起来像这样 问题答案: 对于第一个问题,您应该做的第一件事是使用运算符模块中的itemgetter按第二个字段对

  • 问题内容: 我想对整数的arraylist的arraylist进行排序,需要帮助吗? 我被告知,我需要实现比较器或可比对象,然后使用collection.sort对列表列表进行排序… 问题答案: 没有错误检查空列表,但是这里是。 使用Java 8,它变得更加简洁:

  • 问题内容: 从经验上讲,似乎Python的默认列表排序器在传递元组列表时将按每个元组中的第一个元素进行排序。那是对的吗?如果不是,按元组的第一个元素对元组列表进行排序的正确方法是什么? 问题答案: 它会自动按元组中的第一个元素对元组列表进行排序,然后按第二个元素进行排序,依此类推,tuple([1,2,3])将排在tuple([1,2,4])之前。如果要覆盖此行为,请将一个callable作为第二

  • 部分排序可以通过std::Partial_sort完成。 部分排序方式 5 7 4 2 8 6 1 9 0 3 在对3个元素进行部分排序之后 0 1 2 7 8 6 5 9 4 3 http://en.cppreference.com/w/cpp/algorithm/partial_sort. 但当某些元素已经排序时,这不是最好的。 还有其他这样的函数可以这样做并利用部分排序数组。