Leistung von Stream.sorted(). Limit()

Question

Java Streams Sport sorted und limit Methoden, die jeweils eine sortierte Version eines Streams zurückgeben und einen Stream zurückgeben nur eine bestimmte Anzahl von Elementen eines Streams zurückgegeben. Wenn diese Operationen nacheinander aufgebracht, wie beispielsweise in:

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

wird die Sortierung in einer Art und Weise durchgeführt wird, der die gesamte Liste sortiert qty Artikel oder sortiert? Mit anderen Worten, wenn qty fest ist, ist diese Operation in O(n)? Die Dokumentation spezifiziert nicht die Leistung dieser Methoden allein oder in Verbindung miteinander.

Der Grund, warum ich frage, ist, dass die offensichtliche imperative Durchführung dieser Operationen wäre, zu sortieren und dann zu begrenzen, Zeit nehmend Θ(n * log(n)). Aber diese Operationen können zusammen in O(n * log(qty)) ausgeführt werden und ein Smart-Streaming-Framework könnte den gesamten Stream vor der Ausführung anzeigen, um diesen speziellen Fall zu optimieren.

Answer 1

Lassen Sie mich mit dem allgemeinen Punkt beginnen, dass die Java-Sprachspezifikation der Implementierung von Streams nur wenige Einschränkungen auferlegt. Es ist also wirklich nicht sinnvoll, nach der Leistung von Java-Streams zu fragen: Es wird zwischen Implementierungen sehr unterschiedlich sein.

Beachten Sie auch, dass Stream eine Schnittstelle ist. Sie können Ihre eigene Klasse erstellen, die Stream implementiert, um eine beliebige Leistung oder ein spezielles Verhalten für sorted, die Sie möchten, zu haben. Die Frage nach der Leistung von Stream macht also selbst im Rahmen einer Implementierung keinen Sinn. Die OpenJDK-Implementierung verfügt über viele Klassen, die die Schnittstelle Stream implementieren.

Wenn wir uns die OpenJDK-Implementierung anschauen, die Sortierung von Streams endet in der SortedOps-Klasse (siehe Quelle here), werden Sie feststellen, dass die Sortiermethoden am Ende Erweiterungen von Stateful-Operationen zurückgeben. Zum Beispiel:

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

überprüfen Diese Methoden, wenn der stromaufwärts bereits in denen sortiert Fall, dass sie es nur auf den nachgelagerten passieren. Sie haben auch spezielle Ausnahmen für sortierte Streams (d. H. Upstream), die die Arrays vorsortieren, die sie am Ende sortieren, was die Effizienz verbessert (über eine SpinedBuffer, die sie für Streams unbekannter Größe verwenden). Aber wenn der Upstream nicht bereits sortiert ist, akzeptieren sie alle Elemente, sortieren sie dann und senden sie an die Methode accept der Downstream-Instanz.

Die Schlussfolgerung daraus ist, dass die OpenJDK sorted Implementierung alle Elemente sammelt, sortiert und dann sendet nach unten. In einigen Fällen wird dies Ressourcen verschwenden, wenn der Downstream einige Elemente verwerfen wird. Es steht Ihnen frei, eine eigene spezielle Sortieroperation zu implementieren, die für Sonderfälle effizienter ist.Der einfachste Weg ist die Implementierung einer Collector, die eine Liste der n größten oder kleinsten Elemente im Stream enthält. Ihr Betrieb könnte dann in etwa so aussehen:

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

Um

.sorted().limit(4) 

Answer 2

Das ist implementierungsabhängig und hängt möglicherweise auch davon ab, ob die Stream-Pipeline potenzielle Operationen zwischen sorted() und limit() "durchschauen" kann.

Auch wenn Sie nach der OpenJDK-Implementierung gefragt haben, können Änderungen vorgenommen werden, da die Javadocs keine Garantie für das Laufzeitverhalten übernehmen. Aber nein, derzeit implementiert es keinen k-min-Auswahlalgorithmus.

Sie müssen auch bedenken, dass sorted() funktioniert nicht auf unendlich Streams, wenn sie bereits die SORTED-Eigenschaft haben.

Answer 3

Es gibt einen speziellen Sammler in meiner StreamEx Bibliothek zu ersetzen, die diese Operation durchführt: MoreCollectors.least(qty):

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

Es uses Priorityqueue innen und arbeitet tatsächlich wesentlich schneller mit kleinen Mengen auf unsortierten Eingängen. Beachten Sie jedoch, dass wenn die Eingabe meistens sortiert ist, sorted().limit(qty) schneller arbeitet, da TimSort unglaublich schnell für vorsortierte Daten ist.