T
- このスプリッテレータから返される要素の型public interface Spliterator<T>
Collection
、IOチャネル、ジェネレータ関数などです。
スプリッテレータは、要素を個々にトラバースするか(tryAdvance()
)、順次に一括でトラバースする(forEachRemaining()
)ことができます。
また、スプリッテレータはその要素の一部を分割して(trySplit()
を使用)、並列処理に使用する別のスプリッテレータを作成することもできます。分割できない、または分割するとバランスや効率が悪くなるようなスプリッテレータを使用した処理では、並列性の利点が活かされる可能性は低くなります。トラバースと分割は要素を使い果たします。各スプリッテレータは1つの一括計算だけに役立ちます。
また、スプリッテレータはその構造、ソース、および要素の一連の特性(characteristics()
)を、ORDERED
、DISTINCT
、SORTED
、SIZED
、NONNULL
、IMMUTABLE
、CONCURRENT
およびSUBSIZED
の中から返します。これらは、スプリッテレータのクライアントが計算を制御、特殊化、または簡素化するために使用できます。たとえば、Collection
のスプリッテレータはSIZED
を報告し、Set
のスプリッテレータはDISTINCT
を報告し、SortedSet
のスプリッテレータはSORTED
も報告します。特性は、単純に論理和を取ったビット・セットとして報告されます。いくつかの特性は、メソッドの動作を追加で制約します。たとえば、ORDERED
の場合、トラバース・メソッドはそのドキュメント化された順序付けに従う必要があります。将来、新しい特性が定義される可能性があるため、リストにない値に実装側で意味を割り当てないようにしてください。
IMMUTABLE
またはCONCURRENT
を報告しないスプリッテレータは、スプリッテレータが要素ソースにバインドするタイミングと、バインド後に検出された要素ソースの構造的干渉の検出に関して、ドキュメント化されたポリシーを持つことを期待されます。遅延バインディングのスプリッテレータは、スプリッテレータの作成時ではなく、最初のトラバース、最初の分割、または推定サイズの最初の問合せの時点で要素のソースにバインドします。遅延バインディングでないスプリッテレータは、構築時または任意のメソッドの最初の呼出し時に要素のソースにバインドします。バインドの前にソースに加えられた変更は、スプリッテレータがトラバースされるときに反映されます。バインド後、構造的干渉が検出された場合、スプリッテレータはベスト・エフォート・ベースでConcurrentModificationException
をスローするべきです。これを行うスプリッテレータはフェイルファストと呼ばれます。スプリッテレータの一括トラバース・メソッド(forEachRemaining()
)は、トラバースを最適化し、要素ごとにチェックしてすぐに失敗するのではなくすべての要素がトラバースされた後で構造的干渉がないかどうかをチェックすることができます。
スプリッテレータはestimateSize()
メソッドを介して残りの要素数の推定値を提供できます。理想的には、SIZED
特性に反映されるとおり、この値は正常なトラバースで検出される要素の数に正確に一致します。ただし、正確にはわからなくても、ソースに対して実行中の処理で推定値が役立つ場合があります。たとえば、残りの要素をさらに分割する方がよいか順次トラバースする方がよいかを判定するのに役立ちます。
並列アルゴリズムでの有用性は明らかですが、スプリッテレータはスレッドセーフとは見なされません。スプリッテレータを使用して並列アルゴリズムを実装する場合は、一度に1つのスレッドのみがスプリッテレータを使用するようにしてください。通常、これは順次スレッド拘束によって簡単に実現できます。多くの場合、これは再帰的分解によって機能する通常の並列アルゴリズムから自然に得られる結果です。trySplit()
を呼び出しているスレッドが、返されたスプリッテレータを別のスレッドに渡し、次にそのスレッドが、そのスプリッテレータをトラバースするかさらに分割できます。2つ以上のスレッドが同時に同じスプリッテレータを操作した場合の、分割およびトラバースの動作は定義されていません。元のスレッドから別のスレッドに処理のためにスプリッテレータを渡す場合は、いずれかの要素がtryAdvance()
で消費される前に渡すことが最善です。これは、いくつかの保証(SIZED
スプリッテレータのestimateSize()
の正確さなど)はトラバースの開始前にのみ有効なためです。
int
、long
およびdouble
値用にプリミティブ特化されたSpliterator
のサブタイプが用意されています。tryAdvance(java.util.function.Consumer)
およびforEachRemaining(java.util.function.Consumer)
のサブタイプのデフォルト実装は、プリミティブ値をそれに対応するラッパー・クラスのインスタンスにボックス化します。そのようなボックス化を行うと、プリミティブ特化を使用することで得られるパフォーマンス上の利点が薄れる場合があります。ボクシングを避けるには、対応するプリミティブ・ベース・メソッドを使用してください。たとえば、Spliterator.OfInt.tryAdvance(java.util.function.Consumer)
とSpliterator.OfInt.forEachRemaining(java.util.function.Consumer)
よりも、Spliterator.OfInt.tryAdvance(java.util.function.IntConsumer)
とSpliterator.OfInt.forEachRemaining(java.util.function.IntConsumer)
を優先的に使用するべきです。ボックス化ベースのメソッドtryAdvance()
およびforEachRemaining()
を使用してプリミティブ値をトラバースする場合、変換後のボックス化された値が検出される順序は影響を受けません。
Iterators
などのスプリッテレータは、1つのソースの要素をトラバースするためのものです。Spliterator
APIは、分解と単一要素反復処理をサポートすることにより、順次トラバースだけでなく効率のよい並列トラバースをサポートするために設計されました。さらに、スプリッテレータを介して要素にアクセスするためのプロトコルは、要素ごとのオーバーヘッドがIterator
よりも小さくなるように設計されています。また、hasNext()
とnext()
に別々のメソッドがあるため本質的に競合の可能性がありますが、それを回避するように設計されています。
可変ソースの場合は、スプリッテレータがそのデータ・ソースにバインドした時点とトラバースの終了時点との間で、ソースが構造的干渉(要素の追加、置換、削除)を受けていると、非決定論的な任意の動作が発生する可能性があります。たとえば、そのような干渉があると、java.util.stream
フレームワークを使用するときに非決定論的な任意の結果が生成されます。
ソースの構造的干渉は次の方法で管理できます(望ましい順)。
CopyOnWriteArrayList
のインスタンスは不変のソースです。そのソースから作成されたスプリッテレータは、IMMUTABLE
特性を報告します。ConcurrentHashMap
のキー・セットは並行ソースです。そのソースから作成されたスプリッテレータは、CONCURRENT
特性を報告します。ConcurrentModificationException
をスローします。たとえば、ArrayList
の他、JDKの多くの非並行Collection
クラスが遅延バインディングかつフェイルファストのスプリッテレータを提供します。ConcurrentModificationException
をスローする可能性が高くなります。例を示します。配列を保持する次のようなクラスがあり(例として示すためだけの、あまり役に立たないクラスです)、実際のデータを偶数の場所に格納し、無関係のタグ・データを奇数の場所に格納しているとします。そのスプリッテレータはタグを無視します。
class TaggedArray<T> {
private final Object[] elements; // immutable after construction
TaggedArray(T[] data, Object[] tags) {
int size = data.length;
if (tags.length != size) throw new IllegalArgumentException();
this.elements = new Object[2 * size];
for (int i = 0, j = 0; i < size; ++i) {
elements[j++] = data[i];
elements[j++] = tags[i];
}
}
public Spliterator<T> spliterator() {
return new TaggedArraySpliterator<>(elements, 0, elements.length);
}
static class TaggedArraySpliterator<T> implements Spliterator<T> {
private final Object[] array;
private int origin; // current index, advanced on split or traversal
private final int fence; // one past the greatest index
TaggedArraySpliterator(Object[] array, int origin, int fence) {
this.array = array; this.origin = origin; this.fence = fence;
}
public void forEachRemaining(Consumer<? super T> action) {
for (; origin < fence; origin += 2)
action.accept((T) array[origin]);
}
public boolean tryAdvance(Consumer<? super T> action) {
if (origin < fence) {
action.accept((T) array[origin]);
origin += 2;
return true;
}
else // cannot advance
return false;
}
public Spliterator<T> trySplit() {
int lo = origin; // divide range in half
int mid = ((lo + fence) >>> 1) & ~1; // force midpoint to be even
if (lo < mid) { // split out left half
origin = mid; // reset this Spliterator's origin
return new TaggedArraySpliterator<>(array, lo, mid);
}
else // too small to split
return null;
}
public long estimateSize() {
return (long)((fence - origin) / 2);
}
public int characteristics() {
return ORDERED | SIZED | IMMUTABLE | SUBSIZED;
}
}
}
java.util.stream
パッケージなどの並列計算フレームワークでスプリッテレータがどのように並列計算に使用されるかを示す例として、関連する並列のforEachを実装する次のような方法があります。これは、作業の推定量が順次実行できるほど十分小さくなるまでサブタスクを分割していく主な使用方法を示しています。ここでは、サブタスク間の処理順序は重要でないと仮定しています。異なる(フォークされた)タスクがさらに要素を分割して不定の順序で並行処理する場合もあります。この例では、CountedCompleter
を使用しています。同様の使用方法は、他の並列タスク構築にも適用されます。
static <T> void parEach(TaggedArray<T> a, Consumer<T> action) {
Spliterator<T> s = a.spliterator();
long targetBatchSize = s.estimateSize() / (ForkJoinPool.getCommonPoolParallelism() * 8);
new ParEach(null, s, action, targetBatchSize).invoke();
}
static class ParEach<T> extends CountedCompleter<Void> {
final Spliterator<T> spliterator;
final Consumer<T> action;
final long targetBatchSize;
ParEach(ParEach<T> parent, Spliterator<T> spliterator,
Consumer<T> action, long targetBatchSize) {
super(parent);
this.spliterator = spliterator; this.action = action;
this.targetBatchSize = targetBatchSize;
}
public void compute() {
Spliterator<T> sub;
while (spliterator.estimateSize() > targetBatchSize &&
(sub = spliterator.trySplit()) != null) {
addToPendingCount(1);
new ParEach<>(this, sub, action, targetBatchSize).fork();
}
spliterator.forEachRemaining(action);
propagateCompletion();
}
}
org.openjdk.java.util.stream.tripwire
がtrue
に設定されている場合、プリミティブ・サブタイプ特殊化に対する操作時にプリミティブ値のボクシングが発生すると、診断警告が報告されます。Collection
修飾子と型 | インタフェースと説明 |
---|---|
static interface |
Spliterator.OfDouble
double 値に特化されたスプリッテレータです。 |
static interface |
Spliterator.OfInt
int 値に特化されたスプリッテレータです。 |
static interface |
Spliterator.OfLong
long 値に特化されたスプリッテレータです。 |
static interface |
Spliterator.OfPrimitive<T,T_CONS,T_SPLITR extends Spliterator.OfPrimitive<T,T_CONS,T_SPLITR>>
プリミティブ値に特化されたスプリッテレータです。
|
修飾子と型 | フィールドと説明 |
---|---|
static int |
CONCURRENT
外部同期を使用せずに、複数のスレッドで並行して要素のソースを安全に変更できる(追加、置換、削除が可能)ことを示す特性値です。
|
static int |
DISTINCT
検出された要素の各ペア
x, y に対して!x.equals(y) であることを示す特性値です。 |
static int |
IMMUTABLE
要素のソースが構造的に変更不可であることを示す特性値です。つまり、要素の追加、置換および削除ができないため、トラバース中に変更が発生する可能性はありません。
|
static int |
NONNULL
ソースで検出される要素が
null ではないことが保証されることを示す特性値です。 |
static int |
ORDERED
要素の検出順序が定義されていることを示す特性値です。
|
static int |
SIZED
構造的なソース変更がない場合に、トラバースまたは分割の前に
estimateSize() から返される値が完全なトラバースで検出される要素数の正確なカウントを表す有限サイズを表すことを示す特性値です。 |
static int |
SORTED
検出順序が定義済みのソート順序に従うことを示す特性値です。
|
static int |
SUBSIZED
|
修飾子と型 | メソッドと説明 |
---|---|
int |
characteristics()
このスプリッテレータおよびその要素の、一連の特性を返します。
|
long |
estimateSize()
forEachRemaining(java.util.function.Consumer<? super T>) のトラバースで検出される要素数の推定値を返します。無限大または不明の場合、あるいはコストが高すぎて計算できない場合は、Long.MAX_VALUE を返します。 |
default void |
forEachRemaining(Consumer<? super T> action)
すべての要素の処理が完了するかアクションから例外がスローされるまで、現在のスレッド内で残りの各要素に対して指定されたアクションをシーケンシャルに実行します。
|
default Comparator<? super T> |
getComparator()
|
default long |
getExactSizeIfKnown()
|
default boolean |
hasCharacteristics(int characteristics)
指定されたすべての特性がこのスプリッテレータの
characteristics() に含まれている場合はtrue を返します。 |
boolean |
tryAdvance(Consumer<? super T> action)
残りの要素が存在する場合は、指定されたアクションをそれに対して実行し、
true を返します。それ以外の場合はfalse を返します。 |
Spliterator<T> |
trySplit()
このspliteratorをパーティション化できる場合に、要素に適用されるSpliteratorを返します。このメソッドから戻ると同時に、それらの要素にはこのSpliteratorが適用されなくなります。
|
static final int ORDERED
trySplit()
メソッドが要素の厳密な接頭辞を分割すること、tryAdvance(java.util.function.Consumer<? super T>)
メソッドが1要素だけ接頭辞順に進むこと、および、forEachRemaining(java.util.function.Consumer<? super T>)
メソッドがアクションを検出順に実行することを保証します。
対応するCollection.iterator()
で順序がドキュメント化されている場合、Collection
には検出順序があります。その場合、検出順序は、ドキュメント化されている順序と同じです。それ以外の場合、コレクションに検出順序はありません。
static final int DISTINCT
static final int SORTED
getComparator()
メソッドは、関連するコンパレータを返します。あるいは、すべての要素がComparable
で、その自然順序付けに従ってソートされている場合は、null
を返します。
SORTED
を報告するスプリッテレータは、ORDERED
も報告する必要があります。
Collection
クラスのスプリッテレータで、NavigableSet
またはSortedSet
を実装しているものは、SORTED
を報告します。static final int SIZED
estimateSize()
から返される値が完全なトラバースで検出される要素数の正確なカウントを表す有限サイズを表すことを示す特性値です。static final int NONNULL
null
ではないことが保証されることを示す特性値です。(これはたとえば、並行処理コレクション、キューおよびマップの多くに当てはまります。)static final int IMMUTABLE
IMMUTABLE
またはCONCURRENT
を報告しないスプリッテレータは、トラバース中に検出された構造的干渉に関して、ドキュメント化されたポリシー(ConcurrentModificationException
のスローなど)を持つことを期待されます。static final int CONCURRENT
トラバース中にソースが並行して変更された場合に、既知の有限サイズは変化する可能性があるため、最上位のスプリッテレータはCONCURRENT
とSIZED
の両方を報告するべきではありません。そのようなスプリッテレータには一貫性がなく、そのスプリッテレータを使用した計算については何も保証できません。サブスプリッテレータは、サブ分割サイズがわかっている場合で、ソースに対する追加や削除がトラバース中に反映されないときは、SIZED
を報告できます。
static final int SUBSIZED
trySplit()
で生成されたすべてのスプリッテレータがSIZED
とSUBSIZED
の両方であることを示す特性値です。(これは、直接の子か間接の子かを問わず、すべての子スプリッテレータがSIZED
になることを意味します。)
SUBSIZED
によって要求されるとおりにSIZED
を報告しないスプリッテレータには一貫性がなく、そのスプリッテレータを使用した計算については何も保証できません。
SIZED
を報告しますがSUBSIZED
は報告しません。これは、ツリー全体のサイズがわかっても、サブツリーの正確なサイズはわからないことがよくあるためです。boolean tryAdvance(Consumer<? super T> action)
true
を返します。それ以外の場合はfalse
を返します。このスプリッテレータがORDERED
である場合、検出順で次の要素に対してアクションが実行されます。アクションによってスローされた例外は、呼出し側に中継されます。action
- アクションfalse
、それ以外の場合はtrue
。NullPointerException
- 指定されたアクションがnullである場合default void forEachRemaining(Consumer<? super T> action)
ORDERED
である場合、検出順にアクションが実行されます。アクションによってスローされた例外は、呼出し側に中継されます。false
が返されるまで、繰り返しtryAdvance(java.util.function.Consumer<? super T>)
を呼び出します。可能な場合は常にオーバーライドしてください。action
- アクションNullPointerException
- 指定されたアクションがnullである場合Spliterator<T> trySplit()
このスプリッテレータがORDERED
である場合、返されるスプリッテレータは要素の厳密な接頭辞をカバーする必要があります。
このスプリッテレータが無限の要素数をカバーする場合を除き、繰り返しtrySplit()
を呼び出すと、最終的にはnull
が返されるはずです。null以外が返されたときは次のようになります。
estimateSize()
で報告される値は、分割後のこのスプリッテレータおよび返されたスプリッテレータのestimateSize()
と等しいかそれより大きくなければなりません。さらに、SUBSIZED
である場合、分割前のこのスプリッテレータのestimateSize()
は、分割後のこのスプリッテレータおよび返されたスプリッテレータのestimateSize()
の合計と等しくなければなりません。このメソッドはなんらかの理由でnull
を返す場合があります(空であるため、トラバース開始後に分割できないため、データ構造の制約のため、効率上の考慮事項のためなど)。
trySplit
メソッドは、その要素を(トラバースを使用せずに)効率よく、ちょうど半分に分割して、バランスの取れた並列計算を可能にします。この理想から逸脱しても、多くの場合は依然としてかなり効果的です。たとえば、およそのバランスの取れたツリーを単に大まかに分割する場合や、リーフ・ノードに1つまたは2つの要素が含まれているツリーでそれらのノードをさらに分割できない場合です。ただし、バランスが大きく偏っている場合や、trySplit
のメカニズムの効率が非常に悪い場合、通常は、結果として得られる並列処理のパフォーマンスは低くなります。Spliterator
。このスプリッテレータを分割できない場合はnull
long estimateSize()
forEachRemaining(java.util.function.Consumer<? super T>)
のトラバースで検出される要素数の推定値を返します。無限大または不明の場合、あるいはコストが高すぎて計算できない場合は、Long.MAX_VALUE
を返します。
このスプリッテレータがSIZED
であり、まだ部分的にトラバースまたは分割されていない場合、あるいは、このスプリッテレータがSUBSIZED
であり、まだ部分的にトラバースされていない場合、この推定値は完全なトラバースで検出される要素数の正確なカウントでなければなりません。それ以外の場合、この推定値は任意の不正確な値でかまいませんが、trySplit()
の呼出しにわたって、指定されたとおりに減少する必要があります。
Long.MAX_VALUE
。default long getExactSizeIfKnown()
SIZED
特性を報告する場合はestimateSize()
の結果を返し、それ以外の場合は-1
を返します。-1
。int characteristics()
ORDERED
、DISTINCT
、SORTED
、SIZED
、NONNULL
、IMMUTABLE
、CONCURRENT
、SUBSIZED
の値の論理和で表されます。trySplit
の呼出しの前または呼出しと呼出しの間に、1つのスプリッテレータに対して繰り返しcharacteristics()
を呼び出すと、常に同じ結果が返されるはずです。
スプリッテレータが一貫性のない特性セット(1つの呼出しから返されたものか、複数の呼出しから返されたもの)を報告する場合、このスプリッテレータを使用した計算については何も保証できません。
SIZED
、SUBSIZED
およびCONCURRENT
を参照してください。default boolean hasCharacteristics(int characteristics)
characteristics()
に含まれている場合はtrue
を返します。characteristics
- チェックする特性true
、そうでない場合はfalse
default Comparator<? super T> getComparator()
Comparator
によってソートされている(SORTED
)場合は、そのComparator
を返します。ソースが自然順序でソートされている(SORTED
)場合はnull
を返します。それ以外の場合、ソースがソートされて(SORTED
)いないときはIllegalStateException
をスローします。IllegalStateException
をスローします。null
。IllegalStateException
- スプリッテレータがSORTED
特性を報告しない場合。 バグまたは機能を送信
詳細なAPIリファレンスおよび開発者ドキュメントについては、Java SEのドキュメントを参照してください。そのドキュメントには、概念的な概要、用語の定義、回避方法、有効なコード例などの、開発者を対象にしたより詳細な説明が含まれています。
Copyright© 1993, 2014, Oracle and/or its affiliates. All rights reserved.