Списки сортировки после группировки

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

Сначала сортировка, затем группировка в один поток:

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,

Источник

3 ответа

Решение

Когда используешь 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)));

Операция сортировки ведет себя так же (спасибо Тагиру Валееву за исправление), но вы можете легко проверить, как работает стратегия сортировки при вставке. Просто измените реализацию коллектора на:

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 не будет изменять их относительный порядок, если исходный поток имеет определенный порядок встречи.

Источник

Да, мы можем сортировать по полу, а затем сортировать по возрасту в одну строку. Ниже строки кода сначала сортируется по полу, а затем применяется сортировка по возрасту [предполагая, что getGender() и getAge() являются методами получения]. Но здесь сортировка будет основываться на поле.

      roster.stream().sorted(Comparator.comparing(Person::getGender).thenComparing(Person::getAge, String::compareToIgnoreCase)).collect(Collectors.toList()))
Источник

Вы можете использовать компаратор и решить проблему:

class Sorter implements Comparator<Person>{
@Override
public int compare(Person p1, Perspn p2) {
    if(p1.getGender().equals(p2.getGender())) {
        return Integer.compare(p2.getAge(),p1.getAge());
    } else if(p1.getGender().equals("M")){
        return -1;
    } else if(p1.getGender().equals("F")) {
        return 0;
    } 
}

}

Это приведет к тому, что человек будет сгруппирован по полу с возрастом в порядке убывания (где мужчина будет на первом месте, а женщина - на втором)

Источник
Другие вопросы по тегам