イテレータトップ等値性ビュー目次

ビュー

コレクションは新しいコレクションを構築するメソッドを多く備えています。 例えば、map, filter, ++です。 このようなメソッドは少なくとも1つのコレクションをレシーバオブジェクトとして受け取り、結果として他のコレクションを作るため、これらを変換子と呼びます。

変換子を実装する主な方法は2つあります。 1つは正格、すなわち新しいコレクションとその全ての要素を変換子の結果として構築する方法です。 もう1つは非正格つまり遅延、すなわち結果のコレクションの代理のみを構築し、その要素は要求されたときに初めて構築する方法です。

非正格な変換子の例として、以下の遅延写像演算の実装を考えてみます:

def lazyMap[T, U](coll: Iterable[T], f: T => U) = new Iterable[T] {
  def iterator = coll.iterator map f
}

lazyMapは与えられたコレクションcollの全ての要素を辿ることなく新しいIterableを構築している点に注意してください。 代わりに、与えられた関数fは必要となったときに新しいコレクションのiteratorに適用されます。

全ての変換子メソッドを遅延的に実装するStreamを除いて、Scalaのコレクションは変換子について全てデフォルトでは正格です。 然し、コレクションのビューに基づいて全てのコレクションを遅延的なものにしたりその逆にしたりする系統だった方法があります。 ビューとは元となるコレクションの代理となる特別な種類のコレクションで、ただし変換子を遅延的に実装します。

コレクションをそのビューにするにはコレクションのviewメソッドを使います。 もしxsがコレクションであれば、xs.viewは全ての変換子が遅延的に実装されている点を除いて同じコレクションです。 ビューから正格なコレクションに戻すには、forceメソッドが使えます。

例を見てみましょう。 2つの関数を順にマップしたいIntのベクタがあるとします:

scala> val v = Vector(1 to 10: _*)
v: scala.collection.immutable.Vector[Int] =
   Vector(12345678910)
scala> v map (_ + 1) map (_ * 2)
res5: scala.collection.immutable.Vector[Int] = 
   Vector(46810121416182022)

最後の文の式v map (_ + 1)は新しいベクタを構築し、それを2つ目のmap (_ * 2)の呼び出しで3つ目のベクタに変換します。 多くの場合、最初のmapの呼び出しの結果として生じる中間的な結果の構築はやや無駄です。 上の例では、2つの関数(_ + 1)(_ * 2)を合成して1つのmapで済ませた方がより速くなるでしょう。 もし2つの関数が同じ場所にあればこれを手でできるでしょう。 しかし多くの場合、データ構造に対する連続した変換はプログラムの別のモジュールで施されます。 それらの変換を融合するとモジュール性の土台を崩してしまうでしょう。 中間的な結果を防ぐもっと一般的な方法は、まずベクタをビューにし、その後全ての変換をビューに適用し、そして最後にビューをベクタに強制するものです:

scala> (v.view map (_ + 1) map (_ * 2)).force
res12: Seq[Int] = Vector(4, 6, 8, 10, 12, 14, 16, 18, 20, 22)  

この演算の列をもう一回1つずつやってみましょう:

scala> val vv = v.view
vv: scala.collection.SeqView[Int,Vector[Int]] = 
   SeqView(12345678910)

v.viewの適用によりSeqView、つまり遅延的に評価されるSeqが得られます。 型SeqViewは2つの型パラメータを取ります。 最初のIntはビューの要素を示します。 2番目のVector[Int]はビューを強制して戻したときに得られる型コンストラクタを示します。

ビューに最初のmapを適用すると以下のものが得られます:

scala> vv map (_ + 1)
res13: scala.collection.SeqView[Int,Seq[_]] = SeqViewM(...)

mapの結果はSeqViewM(...)と表示する値です。 これは要するにmap(_ + 1)と共にベクトルvに適用する必要があるとう事を記録したラッパーです。 ただし、ビューがforceされるまで写像は適用されません。 SeqViewMの後の“M”はビューがmap演算を包んでいることを示します。 他の文字ならば他の遅延された演算を表します。 例えば“S”は遅延されたslice演算を表しますし、“R”はreverseを表します。 では前の結果に2つ目のmapを適用してみましょう。

scala> res13 map (_ * 2)
res14: scala.collection.SeqView[Int,Seq[_]] = SeqViewMM(...)

すると写像演算を2つ含むSeqViewが得られますので、SeqViewMM(...)という風に2つの“M”が表示されます。 最後に前の結果を強制すると以下の物が得られます:

scala> res14.force
res15: Seq[Int] = Vector(4, 6, 8, 10, 12, 14, 16, 18, 20, 22)

force演算の実行の一部として、保持された関数の両方が適用され、新しいベクタが構築されます。 このように、中間的なデータ構造は必要ありません。

特筆すべき細かい部分として、最終結果の静的な型はVectorではなくSeqであるという点が挙げられます。 型を辿ってみてみると、最初の遅延写像が適用された時点でその結果の静的な型はSeqViewM[Int, Seq[_]]でした。 つまり、ビューが特定の列型Vectorに適用されたという「知識」は失なわれています。 いくつかのクラスに対するビューの実装はとても多くのコードが必要ですので、Scalaのコレクションライブラリは一般的なコレクション型にほとんど限ってビューを提供し、特定の実装には提供していません5

ビューを使いたくなる理由は2つあります。 1つ目は性能です。 コレクションをビューに変えると中間結果を避けられる点を見てきました。 この節約はとても重要です。 他の例として、単語のリストから回文を探す問題を考えてみましょう。 回文とは前から読んでも後ろから読んでも同じになる文です。 必要なコードは以下のようになります:

def isPalindrome(x: String) = x == x.reverse
def findPalidrome(s: Seq[String]) = s find isPalindrome

さて、とても長い列wordsがあり、その列の最初の100万語の中から回文を探したいとしましょう。 findPalidromeの定義を再利用できるでしょうか。 もちろん次のようにも書けるでしょう:

findPalindrome(words take 1000000)

これは最初の列の最初の100万語を取ってくるという側面とその中から回文を探すという側面を上手く分けています。 しかし、欠点としてはたとえ最初の語句が回文であったとしても100万語からなる中間的な列を常に構築してしまうという点が挙げられます。 つまり999,999語が結局全く調べられないのに中間結果へとコピーされてしまいます。 多くのプログラマはここで諦めて引数の列の与えられたプレフィックスから回文を探すように特化したバージョンを書くことでしょう。 しかしビューを使えばその必要はありません。 単に次のように書けばよいのです:

findPalindrome(words.view take 1000000)

これも同じように上手く関心事を分けていますが、100万要素の列を作る代わりに軽量なビューオブジェクトのみを構築しています。 このように、性能かモジュール性かを選ぶ必要はありません。

2つ目の事例では可変な列にビューを適用します。 そのようなビューに対する多くの変換子関数は元の列の一部の要素を選択的に更新するのに使える、列に対する覗き窓を提供します。 これを具体例で見てみるために、配列arrがあるとしましょう:

scala> val arr = (0 to 9).toArray
arr: Array[Int] = Array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

arrのビューのスライスを作ると、この配列の部分窓を作成できます:

scala> val subarr = arr.view.slice(36)
subarr: scala.collection.mutable.IndexedSeqView[
Int,Array[Int]] = IndexedSeqViewS(...)

こうすると配列attの3番目から5番目の要素を参照するビューsubarrが得られます。 ビューは値をコピーせず、それらへの参照を提供するだけです。 さて、列の要素を変更するメソッドがあるとします。 例えば、以下のnegateメソッドは与えられた整数の列の全ての要素の符号を反転します:

scala> def negate(xs: collection.mutable.Seq[Int]) =
         for (i <- 0 until xs.length) xs(i) = -xs(i)
negate: (xs: scala.collection.mutable.Seq[Int])Unit

ここで配列arrの3番目から5番目の要素の符号を反転させたいとします。 ここでnegateを使えるでしょうか。 ビューを使うと簡単にできます:

scala> negate(subarr)
scala> arr
res4: Array[Int] = Array(0, 1, 2, -3, -4, -5, 6, 7, 8, 9)

これはarrのスライスであるsubarrの全要素の符号を反転しています。 ここでもビューはモジュール化を保つのに役立っています。 上記のコードはどのどのメソッドを適用するのかという問題と、どの添字範囲に適用するのかという問題を上手く分けています。

ビューの見事な使い方を見てきたので、一体なぜ正格なコレクションがあるんだと思うかもしれません。 理由の1つは、性能の比較では常に正格なコレクションよりも遅延的なコレクションが有利なわけではない点です。 多くの場合、小さなコレクションではビュー内にクロージャーを作成して適用するオーバーヘッドが中間データ構造を避けて得られる利点よりも大きくなります。 おそらくより重要な理由は遅延された演算が副作用を持つ場合、ビュー内での評価はとてもわかりづらくなることがある点です。

これはScalaの2.8より前のバージョンで何人かのユーザを困らせた例です: 前のバージョンではRangeは遅延的でしたので、事実上ビューの様に振る舞っていました。 人々は複数のアクターをこのように作ろうとしていました:

val actors = for (i <- 1 to 10yield actor { ... }

actorメソッドはその後の括弧内で囲われたコードからアクターを作って開始するはずなのに、驚いたことにその後アクターは1つも実行されませんでした。 なぜ何も起きなかったのか明らかにするために、上記の式はmapの適用と等価あることを思い出してください:

val actors = (1 to 10) map (i => actor { ... })

以前は(1 to 10)によって作られる範囲はビューのように振る舞ったため、mapの結果もビューでした。 つまり、要素は1つも計算されず、よって、結果として、アクターは1つも作られなかったのです! アクターは全体の式である範囲を強制すればアクターは作られたでしょうが、それがアクターを動作させるために必要なものであるとは自明からほど遠いものです。

このような驚きを避けるために、Scala 2.8のコレクションライブラリはもっと一定の規則を備えています。 ストリームとビューを除く全てのコレクションは正則です。 正則なものを遅延的なコレクションにする唯一の方法はviewメソッドによるものです(訳註: マップのfilterKeysmapValuesはビューではないものの遅延的に実行されるマップを返す。また、TraversableのwithFilterのフィルタも遅延的に実行される。また、イテレータもビューのようにふるまう)。 元に戻す唯一の方法はforceによる方法です。 そのため、上記のactorsの定義はScala 2.8では10個のアクターを作って開始するという風に期待した通りに動くでしょう。 元の意外な動きに戻す場合にはviewメソッドの明示的な呼び出しを加える必要があります:

val actors = for (i <- (1 to 10).view) yield actor { ... }

要約としては、ビューは効率への関心とモジュール性への関心を調和させる強力なツールです。 しかし遅延評価という側面に巻き込まれないようにするためには、ビューを2つの場合に限るべきです。 コレクションの変換子が副作用を持たない純粋に関数的なコードでのみビューを適用してください。 もしくは全ての変更が明示的に実施される場合には可変なコレクションに適用してください。 最も避けるべきはビューと、副作用を持ちながら新しいコレクションを作る演算の混合です。

続いては: イテレータ


イテレータトップ等値性ビュー目次