モジュール java.base
パッケージ java.util

インタフェースSpliterator<T>

型パラメータ:
T - このスプリッテレータから返される要素の型
既知のすべてのサブインタフェース:
Spliterator.OfDouble, Spliterator.OfInt, Spliterator.OfLong, Spliterator.OfPrimitive<T,T_CONS,T_SPLITR>
既知のすべての実装クラス:
Spliterators.AbstractDoubleSpliterator, Spliterators.AbstractIntSpliterator, Spliterators.AbstractLongSpliterator, Spliterators.AbstractSpliterator
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をレポートしないスプリッタには、次のポリシーに関する文書化が必要です: スプリッタバインドから要素ソース、およびバインド後に検出された要素ソースの構造的干渉の検出。 late-bindingスプリッタは、スプリッタの作成時ではなく、最初の走査、最初の分割、または推定サイズの最初の問合せの時点で要素のソースにバインドします。 遅延バインディングでないスプリッテレータは、構築時または任意のメソッドの最初の呼出し時に要素のソースにバインドします。 バインドの前にソースに加えられた変更は、スプリッテレータがトラバースされるときに反映されます。 バインド後、構造的干渉が検出された場合、スプリッテレータはベスト・エフォート・ベースで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.OfPrimitive.tryAdvance(java.util.function.IntConsumer)およびSpliterator.OfPrimitive.forEachRemaining(java.util.function.IntConsumer)は、Spliterator.OfInt.tryAdvance(java.util.function.Consumer)およびSpliterator.OfInt.forEachRemaining(java.util.function.Consumer)よりも優先して使用する必要があります。 ボックス化ベースのメソッドtryAdvance()およびforEachRemaining()を使用してプリミティブ値をトラバースする場合、変換後のボックス化された値が検出される順序は影響を受けません。

APIのノート:

Iteratorのようなスプリッタは、ソースの要素をトラバースするためのものです。 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に設定されている場合、プリミティブ・サブタイプの特殊化時にプリミティブ値のボックス化が発生すると、診断警告がレポートされます。
導入されたバージョン:
1.8
関連項目: