Die effizienteste Sammlung zum Filtern eines Java-Streams?

Question

Ich speichere mehrere Thing s in einer Sammlung. Die einzelnen Thing s sind einzigartig, aber ihre Typen sind nicht. Die Reihenfolge, in der sie gespeichert sind, spielt keine Rolle.

Ich möchte Java 8 Stream API verwenden, um es für eine bestimmte Art mit diesem Code zu suchen:

Collection<Thing> things = ...; 
// ... populate things ... 
Stream<Thing> filtered = things.stream.filter(thing -> thing.type.equals(searchType)); 

Gibt es einen bestimmten Collection, dass die filter() effizienter machen würde?

Ich bin geneigt, Nein zu denken, weil der Filter durch die gesamte Sammlung iterieren muss.

Auf der anderen Seite, wenn die Sammlung eine Art von Baum ist, der von der Thing.type indiziert wird, dann könnte die filter() in der Lage sein, diese Tatsache zu nutzen. Gibt es einen Weg, dies zu erreichen?

Answer 1

Soweit ich weiß, gibt es keine solche Unterscheidung für das normale Streaming.

Sie können jedoch besser arbeiten, wenn Sie paralleles Streamen verwenden, wenn Sie eine Sammlung verwenden, die leicht abgrenzbar ist, z. B. ArrayList über LinkedList oder eine andere Art von Set.

Answer 2

Die Stream-Operationen wie Filter sind nicht so spezialisiert, um in speziellen Fällen einen Vorteil zu haben. Zum Beispiel wird IntStream.range(0, 1_000_000_000).filter(x -> x > 999_999_000) tatsächlich alle Eingabenummern iterieren, es kann nicht einfach die erste 999_999_000 "überspringen". So wird Ihre Frage reduziert, um die Sammlung mit der effizientesten Iteration zu finden.

Die Iteration wird in der Regel in Spliterator.forEachRemaining Verfahren (für Nicht-Kurzschlussstrom) und in Spliterator.tryAdvance Verfahren (zum Kurzschließen Strom) durchgeführt, so dass Sie einen Blick in die entsprechende spliterator Implementierung nehmen und prüfen, wie effizient es ist . Meiner Meinung nach ist das effizienteste Array (entweder leer oder in Liste mit Arrays.asList verpackt): es hat minimalen Overhead. ArrayList ist auch ziemlich schnell, aber für den Kurzschlussbetrieb wird es die modCount (um gleichzeitige Änderung zu erkennen) bei jeder Iteration überprüfen, die sehr geringen Overhead hinzufügen würde. Andere Typen wie HashSet oder LinkedList sind vergleichsweise langsamer, obwohl dieser Unterschied in den meisten Anwendungen praktisch unbedeutend ist.

Beachten Sie, dass parallele Streams mit Vorsicht verwendet werden sollten. Zum Beispiel ist die Aufspaltung von LinkedList ziemlich schlecht und Sie können eine schlechtere Leistung als im sequentiellen Fall erleben.

Answer 3

Die wichtigste Sache zu verstehen, in Bezug auf diese Frage ist, dass, wenn Sie einen Lambda-Ausdruck an eine bestimmte Bibliothek wie die Stream API übergeben, alle Bibliothek empfängt eine Implementierung einer funktionalen Schnittstelle, z. eine Instanz von Predicate. Es hat keine Kenntnis darüber, was diese Implementierung tun wird, und hat daher keine Möglichkeit, Szenarien wie das Filtern sortierter Daten über Vergleiche zu nutzen. Die Stream-Bibliothek weiß einfach nicht, dass der Predicate einen Vergleich macht.

Eine Implementierung, die eine solche Optimierung durchführt, würde eine Interaktion der JVM, die den Code kennt und versteht, und der Bibliothek, die die Semantik kennt, benötigen. So etwas passiert in der aktuellen Implementierung nicht und ist derzeit weit weg, zumindest so, wie ich es sehen kann.

Wenn die Quelle eine Baum- oder sortierte Liste ist und Sie davon für das Filtern profitieren möchten, müssen Sie vor der Erstellung des Streams APIs verwenden, die auf der Quelle ausgeführt werden. Z.B.nehme an, wir haben eine TreeSet und wollen es filtern, Artikel in einem bestimmten Bereich zu bekommen, wie

// our made-up source 
TreeSet<Integer> tree=IntStream.range(0, 100).boxed() 
    .collect(Collectors.toCollection(TreeSet::new)); 
// the naive implementation 
tree.stream().filter(i -> i>=65 && i<91).forEach(i->System.out.print((char)i.intValue())); 

Wir tun kann stattdessen:

tree.tailSet(65).headSet(91).stream().forEach(i->System.out.print((char)i.intValue())); 

, die die sortierte/Baum Natur werden nutzen. Wenn wir stattdessen eine sortierte Liste haben, sagen

List<Integer> list=new ArrayList<>(tree); 

die sortierte Art unter Verwendung komplexer ist als die Sammlung selbst nicht weiß, dass sie sortiert ist und bietet keine Operationen, die direkt unter Verwendung von:

int ix=Collections.binarySearch(list, 65); 
if(ix<0) ix=~ix; 
if(ix>0) list=list.subList(ix, list.size()); 
ix=Collections.binarySearch(list, 91); 
if(ix<0) ix=~ix; 
if(ix<list.size()) list=list.subList(0, ix); 
list.stream().forEach(i->System.out.print((char)i.intValue())); 

Natürlich sind die Stream-Operationen hier nur beispielhaft und Sie brauchen überhaupt keinen Stream, wenn Sie dann nur forEach ...