Go to Qiita Advent Calendar Top
LoginSignup
10
10

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@okumin

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

Posted at

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
10
10
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
10
10

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?