Wydajność Stream.sorted() .limit()

Question

Strumienie Java mają zarówno metody sorted, jak i limit, które odpowiednio zwracają posortowaną wersję strumienia i zwracają strumień, który właśnie zwraca określoną liczbę elementów strumienia. Gdy operacje te są stosowane z rzędu, takich jak:

stream.sorted().limit(qty).collect(Collectors.toList()) 

jest sortowanie odbywa się w sposób, który sortuje qty przedmiotów lub ma całą listę posortowaną? Innymi słowy, jeśli naprawiono qty, czy ta operacja jest w O(n)? Dokumentacja nie określa wydajności tych metod samych lub w połączeniu ze sobą.

Powodem, dla którego pytam, jest to, że oczywistą konieczną realizacją tych operacji byłoby sortowanie, a następnie ograniczanie, biorąc pod uwagę czas Θ(n * log(n)). Ale te operacje mogą być wykonywane razem w O(n * log(qty)), a inteligentna struktura przesyłania strumieniowego może wyświetlić cały strumień przed wykonaniem go, aby zoptymalizować ten specjalny przypadek.

Answer 1

Zacznę od ogólnego stwierdzenia, że ​​specyfikacja języka Java nakłada pewne ograniczenia dotyczące implementacji strumieni. Tak naprawdę nie jest zbyt ważne, aby zapytać o wydajność strumieni Java: będzie się znacznie różnić między implementacjami.

Należy również pamiętać, że interfejs to Stream. Możesz utworzyć własną klasę, która implementuje Stream, aby uzyskać dowolną wydajność lub specjalne zachowanie na poziomie sorted. Tak naprawdę pytanie o wydajność Stream nie ma sensu nawet w kontekście jednej implementacji. Implementacja OpenJDK ma wiele klas, które implementują interfejs Stream.

Powiedziawszy to, jeśli przyjrzymy się implementacji OpenJDK, sortowanie strumieni kończy się w klasie SortedOps (patrz źródło here), przekonasz się, że metody sortowania kończą się powracaniem rozszerzeń operacji stanowych. Na przykład:

private static final class OfInt extends IntPipeline.StatefulOp<Integer> 

Te metody sprawdzają, czy wcześniejszy kanał jest już posortowany, w takim przypadku przekazują go do dalszego przetwarzania. Mają także specjalne wyjątki dla strumieni o rozmiarach (tj. W górę), które wstępnie alokują tablice, które ostatecznie sortują, co poprawi efektywność (ponad SpinedBuffer, której używają dla strumieni o nieznanym rozmiarze). Ale zawsze, gdy poprzedni element nie jest jeszcze posortowany, akceptują wszystkie elementy, a następnie sortują je, a następnie wysyłają do metody późniejszej instancji.

Wniosek stąd jest taki, że implementacja OpenJDK sorted zbiera wszystkie elementy, a następnie sortuje, a następnie przesyła dalej. W niektórych przypadkach będzie to marnowanie zasobów, gdy dalszy użytkownik odrzuci niektóre elementy. Możesz zaimplementować własną wyspecjalizowaną operację sortowania, która jest bardziej wydajna niż w przypadku specjalnych przypadków.Prawdopodobnie najprostszym sposobem jest zaimplementowanie Collector, który przechowuje listę n największych lub najmniejszych elementów w strumieniu. Twoja praca może wtedy wyglądać następująco:

.collect(new CollectNthLargest(4)).stream() 

Aby wymienić

.sorted().limit(4) 

Answer 2

Jest to zależne od implementacji i może również zależeć od tego, czy potok strumienia może "przejrzeć" potencjalne operacje między sorted() i .

Nawet jeśli miałbyś zapytać o implementację OpenJDK, to może ulec zmianie, ponieważ javadocs nie gwarantują zachowania środowiska wykonawczego. Ale nie, obecnie nie implementuje algorytmu wyboru k-min.

Należy również pamiętać, że sorted() nie działa na nieskończonych strumieniach, o ile nie mają one już charakterystyki SORTED.

Answer 3

Istnieje specjalny kolektor w moim StreamEx biblioteki, która wykonuje tę operację: MoreCollectors.least(qty):

List<?> result = stream.collect(MoreCollectors.least(qty)); 

To uses kolejka priorytetowa wewnątrz i faktycznie działa znacznie szybciej przy małej ilości na niesortowanych danych wejściowych. Zauważ jednak, że jeśli dane wejściowe są w większości sortowane, wtedy sorted().limit(qty) może działać szybciej, ponieważ TimSort jest niewiarygodnie szybki do sortowania danych.