Javaストリームをフィルタリングするのに最も効率的なコレクションですか？

Question

私はコレクションにいくつかのThingを保管しています。個々のThingは一意ですが、その種類は異なります。それらが格納される順序も重要ではありません。

私はこのコードで特定のタイプのためにそれを検索するためのJava 8のストリームAPIを使用したい

：

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

ありfilter()をより効率的になるだろう特定のCollection？

フィルタはコレクション全体を反復処理する必要があるため、いいえと考える傾向があります。

一方、コレクションがThing.typeによってインデックスされた何らかの種類のツリーである場合、filter()はその事実を利用することができます。これを達成する方法はありますか？

Answer 1

私が知っている限り、通常のストリーミングにはそのような違いはありません。

しかし、Parallel Streamingを使用すると、LinkListや他のタイプのSetのArrayListのように、簡単に破棄できるコレクションを使用した方がよい場合があります。

Answer 2

フィルタのようなストリーム操作は、特別な場合に特化するように特化されたものではありません。たとえば、IntStream.range(0, 1_000_000_000).filter(x -> x > 999_999_000)は実際にすべての入力番号を繰り返します。最初の999_999_000を単にスキップすることはできません。したがって、あなたの質問は、最も効率的な反復でコレクションを見つけるために削減されます。

通常、反復はSpliterator.forEachRemaining（非短絡ストリームの場合）とSpliterator.tryAdvance（短絡ストリームの場合）の方法で実行されるため、対応するスプライテータの実装を調べて、その効率を調べることができます。私の意見では、最も効率的なのは、配列（裸であるか、リストにまとめられたArrays.asList）です。最小限のオーバーヘッドしかありません。 ArrayListも非常に速いですが、短絡操作では、わずかなオーバーヘッドを追加するすべての反復でmodCount（同時の変更を検出するために）をチェックします。 HashSetまたはLinkedListのような他のタイプは、比較的遅いですが、ほとんどのアプリケーションでこの違いはほとんどありません。

パラレルストリームは注意して使用する必要があることに注意してください。たとえば、LinkedListの分割は非常に貧弱で、連続した場合よりもパフォーマンスが低下する可能性があります。

Answer 3

この質問に関する最も重要なことは、ラムダ式をStream APIのような特定のライブラリに渡すと、すべてのライブラリが受け取るのは機能インターフェイスの実装であるということです。 Predicateのインスタンスその実装が何をするかについての知識がないため、比較によってソートされたデータをフィルタリングするなどのシナリオを悪用する方法はありません。ストリームライブラリは単にPredicateが比較を行っていることを知らない。

このような最適化を行う実装では、コードを認識し理解しているJVMと、セマンティクスを把握しているライブラリとの対話が必要です。そのようなことは現在の実装では起こらず、少なくとも私が見ることができるように、現在は遠く離れています。

ソースがツリーまたはソートされたリストで、フィルタリングのメリットを得たい場合は、ストリームを作成する前に、ソースで操作しているAPIを使用してソースを操作する必要があります。例えば。私たちは、代わりに行うことができます

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

のように、私たちはTreeSetを持っており、特定の範囲内のアイテムを得るためにそれをフィルタリングしたい、としますソート/木の自然を利用する

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

を。

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

：私たちが代わりにソートされたリストを持っている場合は、コレクション自体は、それがソートだということを知っていないと操作は、その直接利用提供していないとして、ソートされた性質を利用

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

はより複雑であると言います

もちろん、ここでのストリーム操作は一例に過ぎず、ストリームを一切必要としません。forEach ...