必要な要素だけを必要な時に、オンデマンドリストを作成できる Scala の Stream

Posted on:2011年1月10日 at 20:01

Stream (scala.collection.immutable.Stream) は、オンデマンドリストのようなもののようだ。必要な時に必要な処理だけを行ってくれ、無限のリストを表現することができる。

の「Chapter 12 Computing with Streams」に Stream の説明がある。

通常のリストを使う場合と、Stream を使う場合と何が異なるのか、「Chapter 12 Computing with Streams」の記載を参考に確認してみる。

お題として、「指定した範囲で、最初の 2 つの素数を取り出す」ケースを考えてみる。
上記を

で試してみて、Stream を使うことで何がうれしいのか？を確認する。

ちなみに、念のため、素数とは、「1 とその数自身以外に正の約数をがない、1 より大きな自然数のこと」のことになる。

ある数が素数かどうかを判定する関数は以下のような関数になる。

scala> def isPrime(n: Int) = n match {
     |   case i if (i <= 1) => false
     |   case _ => List.range(2, n).forall(x => n % x != 0)
     | }
isPrime: (n: Int)Boolean

確認してみる。

scala> isPrime(1)
res0: Boolean = false

scala> isPrime(2)
res1: Boolean = true

scala> isPrime(3)
res2: Boolean = true

scala> isPrime(4)
res3: Boolean = false

1,000 から 10,000 の範囲で、最初の 2 つの素数を求める。

scala> List.range(1000, 10000).filter(isPrime).take(2)
res34: List[Int] = List(1009, 1013)

「1,000 から 10,000 の範囲で、最初の 2 つの素数を求める」という要件に対してはこれで十分だ。
ただ、効率性という点で以下の問題を残す。

欲しいのは最初の 2 つの素数だけなので、それ以降のリストの数に対しての処理は必要なく、上記の大半は無駄な処理となっている。

その無駄を省くにはどうすればよいか？

Avoid computing the tail of a sequence unless that tail is actually necessary for the computation.

tail(リストの先頭の要素を除いた残りの要素) が本当に必要になった時でなければ、その計算処理を行わない

上記が実現できればよさそうである。それを実現できるのが、Stream になる。

Stream はリストと構造、扱い方は似ており、cons と empty を使って作成することができる。

scala> Stream.cons(1, Stream.cons(2, Stream.empty))
res13: Stream.Cons[Int] = Stream(1, ?)

List と比べてみると、同様の構造になっていることがわかる。

scala> 1 :: 2 :: Nil
res14: List[Int] = List(1, 2)

List.range と同様に、Stream.range が存在する。実装は以下のようなイメージになる。

scala> def sRange(start: Int, end: Int): Stream[Int] = {
     |   if (start >= end) Stream.empty[Int]
     |   else Stream.cons(start, sRange(start + 1, end))
     | }
sRange: (start: Int,end: Int)Stream[Int]

List.range が範囲に指定した全ての要素のリストを生成するのに対して、Stream.range は以下の点で異なる。

Scala By Example (PDF) でもふれられているように、Stream.range と List.range は同じように見えるが、それらの実行時の振舞いは完全に異なっている。

また、実行時の振舞いは異なるが、これまで見てきたように、Stream のインターフェイスは List に似ており、ほとんど同様の操作が行える。

では、先ほど List を使って実施した「指定した範囲で、最初の 2 つの素数を取り出す」を Stream で実施してみる。

scala> Stream.range(1000, 10000).filter(isPrime).take(2)
res35: scala.collection.immutable.Stream[Int] = Stream(1009, ?)

Stream(1009, ?) という Stream オブジェクトが返っており、結果からわかるように、対象のリストの先頭(head)は、既に計算されており、残りの要素(tail)は、まだ計算されていない。実際に、最初の 2 つの素数を取り出してみる。

scala> Stream.range(1000, 10000).filter(isPrime).take(2).toList
res38: List[Int] = List(1009, 1013)

やりたいことは、List 版、Stream 版ともに実現できている。効率性という部分でどれくらいの差が出ているのか？
処理時間を測ることでまずは確認してみる。

関数の実行時間を計測するために、以下の関数を使用する。

scala> def Timer(f: => Unit) {
     |   System.gc
     |   val start = System.nanoTime
     |   f
     |   val end = System.nanoTime
     |   println("Elapse time: (%d)".format(end - start))
     | }
Timer: (f: => Unit)Unit

計測する。

scala> Timer(List.range(1000, 10000).filter(isPrime).take(2))
Elapse time: (828786966)

scala> Timer(List.range(1000, 10000).filter(isPrime).take(2))
Elapse time: (793075437)

scala> Timer(List.range(1000, 10000).filter(isPrime).take(2))
Elapse time: (796202936)

scala> Timer(Stream.range(1000, 10000).filter(isPrime).take(2).toList)
Elapse time: (1704650)

scala> Timer(Stream.range(1000, 10000).filter(isPrime).take(2).toList)
Elapse time: (1011036)

scala> Timer(Stream.range(1000, 10000).filter(isPrime).take(2).toList)
Elapse time: (1241596)

同じ結果を得るのに、List を使った場合の所要時間は、Stream を使った場合の約 600 倍となっている。

Stream を使った場合の**「必要な要素だけ」というのは、take(2) にあるように、2 つの素数だけを処理することであり、「必要な時」**は、Stream.range(1000, 10000).filter(isPrime).take(2) の戻り値の Stream オブジェクトに対して、toList を実行したときとなる。

関連記事