Spliterator の characteristics メソッドが返す値まとめ #java

Java 8 で追加されたイテレータインターフェース Spliterator は、そのデータソースに応じた characteristics を保持することができます。
どの特性を持つべきか自明でないケースがあると感じたので、標準ライブラリ経由で作成した Spliterator が返す characteristics の値をまとめてみました。

Spliterator is 何

java.util.Spliterator は Java 8 で新しく追加されたイテレータインターフェースです。
https://docs.oracle.com/javase/jp/8/docs/api/java/util/Spliterator.html

Java のイテレータといえば、古来より java.util.Iterator が存在します。
Spliterator もおおよそはこの Iterator と同じですが、より最適化された API を提供します。

tryAdvance

java.util.Iterator の場合、hasNext メソッドと next メソッドを組み合わせて要素をイテレートします。
hasNext で「次の」要素が存在するかチェックし、存在する場合は next でその要素を取得するというプロトコルです。

Iterator<String> iterator = ……;
while (iterator.hasNext()) {
  System.out.println(iterator.next());
}

一方、Spliterator は「次の」要素を取得するために tryAdvance という単一のメソッドを提供します。
tryAdvance は Spliterator の要素を受け取り、何かを行う Consumer を引数に取ります。
「次の」要素が存在する場合はその要素を Consumer に消化させつつ true を返し、「次の」要素が存在しない場合は Consumer を実行せず false を返します。

Spliterator<String> spliterator = ……;
do { } while (spliterator.tryAdvance(System.out::println));

※単に全要素トラバースするのが目的であれば、java.util.Iterator、java.util.Spliterator ともに forEachRemaining というメソッドを用いた方がよいと思います。

trySplit

インターフェース名にもその機能が見え隠れしていますが、Spliterator はイテレータを分割するための trySplit メソッドを提供します。
これはレシーバである Spliterator の要素を、戻り値となる Spliterator へ分割する API です。

通常単一の Iterator や Spliterator はスレッドセーフではありません。
しかし trySplit で分割された各 Spliterator はそれぞれ別のスレッドで処理できるので、結果として要素を並列にトラバーサルすることが可能となります。
他にも Spliterator は要素数を取得できたり、後述する characteristics の指定ができたりなど、並列・分割統治を強く意識したインターフェースとなっています。
StreamSupport はこの trySplit や、characteristics を用いてストリームを最適化するそうです。

例えば次のように配列から作成した Spliterator の trySplit を呼び出すと、それぞれの Spliterator がちょうど半分ずつの要素を担当するように分割されます。

final int[] xs = {1, 2, 3, 4, 5, 6, 7, 8};
final Spliterator<Integer> a = Spliterators.spliterator(xs, 0);
final Spliterator<Integer> b = a.trySplit();
a.forEachRemaining(System.out::println); // 5, 6, 7, 8
b.forEachRemaining(System.out::println); // 1, 2, 3, 4

調べたかったこと

どのような特性を持つべきか

Spliterator は自身が持つ特徴に基づいて、ヒントを格納することができます。
現在 Spliterator が持つことができる特徴は「CONCURRENT」「DISTINCT」「IMMUTABLE」「NONNULL」「ORDERED」「SIZED」「SORTED」「SUBSIZED」の8つです。

意味は定数名通りで、例えば Set から作られた Spliterator は要素の重複がないことが保証されているから DISTINCT 属性を付与する、配列から作られた Spliterator は要素数がわかっているから SIZED 属性を付与する、といった使い方をします。

ただ要素が1つであることが明白な場合に DISTINCT 属性や SORTED 属性を付与すべきかどうかが自明でなかったりなど、仕様に微妙に不安を感じました。
そこでさまざまな方法で Spliterator を作成し、データ構造と特性の関係を眺めてみることにしました。

結果

調査ケースがかなり多いので、いくつかのパターンに分割して結果をまとめました。
それぞれ Spliterator のソースと生成された Spliterator の具象クラス、Spliterator の characteristics を記載しています。

java.util.Iterator から作成

Spliterators.spliterator と Spliterators.spliteratorUnknownSize でそれぞれ作成してみました。
そのまんまの結果となりました。

ソース	Spliterator の具象クラス	Spliterator の characteristics
サイズ指定あり	java.util.Spliterators\$IteratorSpliterator	SIZED, SUBSIZED
サイズ指定なし	java.util.Spliterators\$IteratorSpliterator	なし

配列や通常のコレクションから作成

データ構造の特性が表現されているように見えます。
ただ、配列をソースとする Spliterator に ORDERED 特性がない点は気になりました。

ソース	Spliterator の具象クラス	Spliterator の characteristics
配列	java.util.Spliterators\$ArraySpliterator	SIZED, SUBSIZED
ArrayList	java.util.ArrayList\$ArrayListSpliterator	ORDERED, SIZED, SUBSIZED
LinkedList	java.util.LinkedList\$LLSpliterator	ORDERED, SIZED, SUBSIZED
HashSet	java.util.HashMap\$KeySpliterator	DISTINCT, SIZED
LinkedHashSet	java.util.Spliterators\$IteratorSpliterator	DISTINCT, ORDERED, SIZED, SUBSIZED
TreeSet	java.util.TreeMap\$KeySpliterator	DISTINCT, ORDERED, SIZED, SORTED
PriorityQueue	java.util.PriorityQueue\$PriorityQueueSpliterator	NONNULL, SIZED, SUBSIZED

並行コレクションから作成

ほぼすべてのパターンで、IMMUTABLE もしくは CONCURRENT 特性が付与されています。
PriorityBlockingQueue にそれらがないのは、ヒープのデータ構造に由来しているのだと思っています。

ソース	Spliterator の具象クラス	Spliterator の特性
CopyOnWriteArrayList	java.util.Spliterators\$ArraySpliterator	IMMUTABLE, ORDERED, SIZED, SUBSIZED
CopyOnWriteArraySet	java.util.Spliterators\$ArraySpliterator	DISTINCT, IMMUTABLE, SIZED, SUBSIZED
ConcurrentSkipListSet	java.util.concurrent.ConcurrentSkipListMap\$KeySpliterator	CONCURRENT, DISTINCT, NONNULL, ORDERED, SORTED
ConcurrentLinkedQueue	java.util.concurrent.ConcurrentLinkedQueue\$CLQSpliterator	CONCURRENT, NONNULL, ORDERED
LinkedBlockingQueue	java.util.concurrent.LinkedBlockingQueue\$LBQSpliterator	CONCURRENT, NONNULL, ORDERED
LinkedTransferQueue	java.util.concurrent.LinkedTransferQueue\$LTQSpliterator	CONCURRENT, NONNULL, ORDERED
PriorityBlockingQueue	java.util.concurrent.PriorityBlockingQueue\$PBQSpliterator	NONNULL, SIZED, SUBSIZED

特殊な制約のあるパターン

Collections クラスを使って作成した不変シングルトンリストや、不変空リストなどを試してみました。
不変空コレクションの characteristics は正直色々足りていない気がします。

ソース	Spliterator の具象クラス	Spliterator の特性
Collections.singletonList	java.util.Collections\$2	DISTINCT, IMMUTABLE, NONNULL, ORDERED, SIZED, SUBSIZED
Collections.singleton	java.util.Collections\$2	DISTINCT, IMMUTABLE, NONNULL, ORDERED, SIZED, SUBSIZED
Collections.emptyList	java.util.Spliterators\$EmptySpliterator\$OfRef	SIZED, SUBSIZED
Collections.emptySet	java.util.Spliterators\$EmptySpliterator\$OfRef	SIZED, SUBSIZED
Collections.emptySortedSet	java.util.TreeMap\$KeySpliterator	DISTINCT, ORDERED, SIZED, SORTED
Spliterators.emptySpliterator	java.util.Spliterators\$EmptySpliterator\$OfRef	SIZED, SUBSIZED

まとめ

様々な方法で Spliterator を作成し、それぞれの characteristics を取得してみました。
おおよその傾向はつかめたものの、標準ライブラリ自体、必ずしも一貫した実装となっているわけではなさそうです。

調査履歴

調査ログです。
長いので結果まとめの参照をオススメします。

Java は「Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_60」です。

前提

Scala REPL で試しました。
あらかじめ次のインポートとメソッド定義を行っておきます。

import java.util._
import java.util.concurrent._
def printCharacteristics[T](spliterator: Spliterator[T]): Unit = {
  println(Seq(
    if (spliterator.hasCharacteristics(Spliterator.CONCURRENT)) Some("CONCURRENT") else None,
    if (spliterator.hasCharacteristics(Spliterator.DISTINCT)) Some("DISTINCT") else None,
    if (spliterator.hasCharacteristics(Spliterator.IMMUTABLE)) Some("IMMUTABLE") else None,
    if (spliterator.hasCharacteristics(Spliterator.NONNULL)) Some("NONNULL") else None,
    if (spliterator.hasCharacteristics(Spliterator.ORDERED)) Some("ORDERED") else None,
    if (spliterator.hasCharacteristics(Spliterator.SIZED)) Some("SIZED") else None,
    if (spliterator.hasCharacteristics(Spliterator.SORTED)) Some("SORTED") else None,
    if (spliterator.hasCharacteristics(Spliterator.SUBSIZED)) Some("SUBSIZED") else None
  ).flatten.mkString(", "))
}

java.util.Iterator から作成

サイズ指定あり

Spliterators.spliterator の第二引数はイテレータのサイズ、第三引数は追加で指定する characteristics です。
例えば要素が null でないことがアプリケーションレベルで保証されている場合、第三引数に NONNULL を指定する、といった使い方ができます。
0を指定すると何も characteristics を追加しません。

scala> val iterator = new java.util.Iterator[Int] {
     |   var i = 0
     |   def hasNext(): Boolean = i < 8
     |   def next(): Int = {
     |     if (i >= 8) throw new NoSuchElementException()
     |     i += 1
     |     i
     |   }
     | }
iterator: java.util.Iterator[Int]{def i: Int; def i_=(x$1: Int): Unit} = $anon$1@1d6dc2b8

scala> val spliterator = Spliterators.spliterator(iterator, 8, 0)
spliterator: java.util.Spliterator[Int] = java.util.Spliterators$IteratorSpliterator@5c8e7687

scala> printCharacteristics(spliterator)
SIZED, SUBSIZED

サイズ指定なし

イテレータはあらかじめ要素数が確定していなかったり、あるいは無限の要素を持つ可能性があります。
そのような場合、Spliterators.spliteratorUnknownSize を用いて Spliterator を作成します。
第二引数はは追加で指定する characteristics です

scala> val iterator = new java.util.Iterator[Int] {
     |   var i = 0
     |   def hasNext(): Boolean = i < 8
     |   def next(): Int = {
     |     if (i >= 8) throw new NoSuchElementException()
     |     i += 1
     |     i
     |   }
     | }
iterator: java.util.Iterator[Int]{def i: Int; def i_=(x$1: Int): Unit} = $anon$1@1c96bf1e

scala> val spliterator = Spliterators.spliteratorUnknownSize(iterator, 0)
spliterator: java.util.Spliterator[Int] = java.util.Spliterators$IteratorSpliterator@44ba9f25

scala> printCharacteristics(spliterator)

配列や通常のコレクションから作成

配列

Array[Int] からそのまま Spliterator を作るとプリミティブ配列に特化した Spliterator ができるので、AnyRef(Java の Object 型)にキャストしています。

scala> val spliterator = Spliterators.spliterator[Int]((1 to 8).toArray.map(_.asInstanceOf[AnyRef]), 0)
spliterator: java.util.Spliterator[Int] = java.util.Spliterators$ArraySpliterator@32ca397b

scala> printCharacteristics(spliterator)
SIZED, SUBSIZED

ArrayList

scala> val collection = new ArrayList[Int]()
collection: java.util.ArrayList[Int] = []

scala> (1 to 8).foreach(collection.add)

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.ArrayList$ArrayListSpliterator@7d3af2f0

scala> printCharacteristics(spliterator)
ORDERED, SIZED, SUBSIZED

LinkedList

scala> val collection = new LinkedList[Int]()
collection: java.util.LinkedList[Int] = []

scala> (1 to 8).foreach(collection.add)

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.LinkedList$LLSpliterator@71637a85

scala> printCharacteristics(spliterator)
ORDERED, SIZED, SUBSIZED

HashSet

scala> val collection = new HashSet[Int]()
collection: java.util.HashSet[Int] = []

scala> (1 to 8).foreach(collection.add)

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.HashMap$KeySpliterator@71daf5d6

scala> printCharacteristics(spliterator)
DISTINCT, SIZED

LinkedHashSet

scala> val collection = new LinkedHashSet[Int]()
collection: java.util.LinkedHashSet[Int] = []

scala> (1 to 8).foreach(collection.add)

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.Spliterators$IteratorSpliterator@28391cc6

scala> printCharacteristics(spliterator)
DISTINCT, ORDERED, SIZED, SUBSIZED

TreeSet

scala> val collection = new TreeSet[Int]()
collection: java.util.TreeSet[Int] = []

scala> (1 to 8).foreach(collection.add)

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.TreeMap$KeySpliterator@62b630e0

scala> printCharacteristics(spliterator)
DISTINCT, ORDERED, SIZED, SORTED

PriorityQueue

scala> val collection = new PriorityQueue[Int]()
collection: java.util.PriorityQueue[Int] = []

scala> (1 to 8).foreach(collection.add)

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.PriorityQueue$PriorityQueueSpliterator@6f75d11b

scala> printCharacteristics(spliterator)
NONNULL, SIZED, SUBSIZED

並行コレクション

CopyOnWriteArrayList

scala> val collection = new CopyOnWriteArrayList[Int]()
collection: java.util.concurrent.CopyOnWriteArrayList[Int] = []

scala> (1 to 8).foreach(collection.add)

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.Spliterators$ArraySpliterator@5a931c02

scala> printCharacteristics(spliterator)
IMMUTABLE, ORDERED, SIZED, SUBSIZED

CopyOnWriteArraySet

scala> val collection = new CopyOnWriteArraySet[Int]()
collection: java.util.concurrent.CopyOnWriteArraySet[Int] = []

scala> (1 to 8).foreach(collection.add)

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.Spliterators$ArraySpliterator@ca024d8

scala> printCharacteristics(spliterator)
DISTINCT, IMMUTABLE, SIZED, SUBSIZED

ConcurrentSkipListSet

scala> val collection = new ConcurrentSkipListSet[Int]()
collection: java.util.concurrent.ConcurrentSkipListSet[Int] = []

scala> (1 to 8).foreach(collection.add)

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.concurrent.ConcurrentSkipListMap$KeySpliterator@7e003cf0

scala> printCharacteristics(spliterator)
CONCURRENT, DISTINCT, NONNULL, ORDERED, SORTED

ConcurrentLinkedQueue

scala> val collection = new ConcurrentLinkedQueue[Int]()
collection: java.util.concurrent.ConcurrentLinkedQueue[Int] = []

scala> (1 to 8).foreach(collection.add)

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.concurrent.ConcurrentLinkedQueue$CLQSpliterator@ffbdb79

scala> printCharacteristics(spliterator)
CONCURRENT, NONNULL, ORDERED

LinkedBlockingQueue

scala> val collection = new LinkedBlockingQueue[Int]()
collection: java.util.concurrent.LinkedBlockingQueue[Int] = []

scala> (1 to 8).foreach(collection.add)

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.concurrent.LinkedBlockingQueue$LBQSpliterator@d57ba2a

scala> printCharacteristics(spliterator)
CONCURRENT, NONNULL, ORDERED

LinkedTransferQueue

scala> val collection = new LinkedTransferQueue[Int]()
collection: java.util.concurrent.LinkedTransferQueue[Int] = []

scala> (1 to 8).foreach(collection.add)

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.concurrent.LinkedTransferQueue$LTQSpliterator@2977084e

scala> printCharacteristics(spliterator)
CONCURRENT, NONNULL, ORDERED

PriorityBlockingQueue

scala> val collection = new PriorityBlockingQueue[Int]()
collection: java.util.concurrent.PriorityBlockingQueue[Int] = []

scala> (1 to 8).foreach(collection.add)

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.concurrent.PriorityBlockingQueue$PBQSpliterator@1fd97710

scala> printCharacteristics(spliterator)
NONNULL, SIZED, SUBSIZED

特殊な制約のあるパターン

Collections.singletonList

要素が１つしかない不変リストです。

scala> val collection = Collections.singletonList(1)
collection: java.util.List[Int] = [1]

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.Collections$2@56625ce9

scala> printCharacteristics(spliterator)
DISTINCT, IMMUTABLE, NONNULL, ORDERED, SIZED, SUBSIZED

Collections.singlton

要素が1つしかない不変セットです。

scala> val collection = Collections.singleton(1)
collection: java.util.Set[Int] = [1]

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.Collections$2@60d501f6

scala> printCharacteristics(spliterator)
DISTINCT, IMMUTABLE, NONNULL, ORDERED, SIZED, SUBSIZED

Collections.emptyList

不変空リストです。

scala> val collection = Collections.emptyList[Int]()
collection: java.util.List[Int] = []

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.Spliterators$EmptySpliterator$OfRef@170f6972

scala> printCharacteristics(spliterator)
SIZED, SUBSIZED

Collections.emptySet

不変空セットです。

scala> val collection = Collections.emptySet[Int]()
collection: java.util.Set[Int] = []

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.Spliterators$EmptySpliterator$OfRef@170f6972

scala> printCharacteristics(spliterator)
SIZED, SUBSIZED

Collections.emptySortedSet

不変空 SortedSet です。

scala> val collection = Collections.emptySortedSet[Int]()
collection: java.util.SortedSet[Int] = []

scala> val spliterator = collection.spliterator()
spliterator: java.util.Spliterator[Int] = java.util.TreeMap$KeySpliterator@d5ce7bb

scala> printCharacteristics(spliterator)
DISTINCT, ORDERED, SIZED, SORTED

Spliterators.emptySpliterator

空 Spliterator です。

scala> val spliterator = Spliterators.emptySpliterator[Int]()
spliterator: java.util.Spliterator[Int] = java.util.Spliterators$EmptySpliterator$OfRef@170f6972

scala> printCharacteristics(spliterator)
SIZED, SUBSIZED