Posted at

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

More than 1 year has passed since last update.


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 という単一のメソッドを提供します。

tryAdvanceSpliterator の要素を受け取り、何かを行う Consumer を引数に取ります。

「次の」要素が存在する場合はその要素を Consumer に消化させつつ true を返し、「次の」要素が存在しない場合は Consumer を実行せず false を返します。

Spliterator<String> spliterator = ……;

do { } while (spliterator.tryAdvance(System.out::println));

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


trySplit

インターフェース名にもその機能が見え隠れしていますが、Spliterator はイテレータを分割するための trySplit メソッドを提供します。

これはレシーバである Spliterator の要素を、戻り値となる Spliterator へ分割する API です。

通常単一の IteratorSpliterator はスレッドセーフではありません。

しかし trySplit で分割された各 Spliterator はそれぞれ別のスレッドで処理できるので、結果として要素を並列にトラバーサルすることが可能となります。

他にも Spliterator は要素数を取得できたり、後述する characteristics の指定ができたりなど、並列・分割統治を強く意識したインターフェースとなっています。

StreamSupport はこの trySplit や、characteristics を用いてストリームを最適化するそうです。

例えば次のように配列から作成した SpliteratortrySplit を呼び出すと、それぞれの 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.spliteratorSpliterators.spliteratorUnknownSize でそれぞれ作成してみました。

そのまんまの結果となりました。

ソース
Spliterator の具象クラス
Spliterator の characteristics

サイズ指定あり
java.util.Spliterators\$IteratorSpliterator
SIZED, SUBSIZED

サイズ指定なし
java.util.Spliterators\$IteratorSpliterator
なし


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

データ構造の特性が表現されているように見えます。

ただ、配列をソースとする SpliteratorORDERED 特性がない点は気になりました。

ソース
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

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

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