sortowanie list według grupy

Question

Zastanawiam się, czy w strumieniach (lub kolekcjonerach) istnieje już zaimplementowana funkcja, która posortowała listy jako wartości. Na przykład. Poniższe kody tworzą zgrupowane według płci listy osób, posortowane według wieku. Pierwsze rozwiązanie ma pewne sortowanie na górze (i wygląda trochę niechlujnie). Drugie rozwiązanie wymaga spojrzenia na każdą osobę dwukrotnie, ale wykonuje ją w ładny sposób.

Pierwszy sortowania następnie grupowanie w jednym strumieniu:

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

pierwszej grupy, a następnie sortowanie każdą wartość:

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

jestem po prostu zastanawiasz się, jeśli istnieje już coś wdrożone, który robi to w jeden bieg, jak groupingBySorted.

Answer 1

Podczas korzystania z sorted(comparator) w strumieniu przed operacją collect strumień musi buforować całą zawartość strumienia, aby można było go posortować, a sortowanie może wymagać znacznie więcej ruchu danych w obrębie tego bufora, w porównaniu do sortowania mniejszych list następnie grupy. Tak więc wydajność nie jest tak dobra, jak sortowanie poszczególnych grup, chociaż implementacja będzie wykorzystywać wiele rdzeni, jeśli włączone jest przetwarzanie równoległe.

Należy jednak pamiętać, że używanie sortedListsByGender.values().forEach(…) nie jest operacją równoległą, a użycie sortedListsByGender.values().parallelStream().forEach(…) umożliwiłoby tylko równoległe przetwarzanie grup, podczas gdy każda operacja sortowania nadal jest sekwencyjna.

Podczas wykonywania operacji sortowania w kolektorze jak w

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

operacja sortowania zachowuje się tak samo (dzięki Tagir Valeev do korygowania mnie), ale można łatwo sprawdzić, jak realizowana jest strategia sortowania na wstawianie. Wystarczy zmienić realizację kolektora do:

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

pod względem kompletności, jeśli chcesz kolektor który wstawia sortowane na na ArrayList w pierwszej kolejności, aby uniknąć końcowy etap kopiowania, można użyć bardziej rozbudowany kolektor tak:

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

Jest wydajny do sekwencyjnego użytkowania, ale jego funkcja łączenia nie jest optymalna. Podstawowy algorytm sortowania będzie korzystał z ustawionych zakresów, ale musi najpierw znaleźć te zakresy, mimo że nasza funkcja scalania faktycznie zna te zakresy. Niestety nie ma publicznego interfejsu API w środowisku JRE, co pozwala nam wykorzystać te informacje (wydajnie: możemy przekazać subList s do binarySearch, ale utworzenie nowej listy podrzędnej dla każdego elementu list2 może okazać się zbyt kosztowne). Jeśli chcemy, aby podnieść wydajność wykonywania równoległego dalej, musimy ponownie wdrożyć część scalania algorytmu Sortowanie:

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

Zauważ, że to ostatnie rozwiązanie, w przeciwieństwie do prostego binarySearch wkładania bazie, jest stabilny sortowanie implementacji, czyli w twoim przypadku, Person s w tym samym wieku i Gender nie zmieni ich względnej kolejności, jeśli strumień źródłowy ma zdefiniowane zlecenie spotkania.

Answer 2

Można użyć komparatora i rozwiązać problem.

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

}

będzie produkować wynik gdzie osoba będzie pogrupowane mądry z wiekiem płeć w celu malejąco (Gdzie mężczyzna przyjdzie w pierwszym miejsce i kobieta w 2)