LL脳がscalaの勉強を始めたよ その82

scala


Scalaコップ本の22章の残りをやっていきますよー、今回はListBufferクラスなどのリストに関するエトセトラデス(´・ω・｀)

ListBufferクラス

リストを構築するよくある処理パターンには再帰がありますデス。この再帰を使うことで、例えばリストの各要素を加工した新たなリストを構築することができますね。サンプルコードとしてはこんな感じのがありますね。サンプルはmapを使わずにリストの各要素をインクリメントする方法デス(´・ω・｀)

def incAll(xs:List[Int]):List[Int] = xs match {
  case List() => List()
  // 先頭に新しい要素（インクリメント済み）を挿入していきます 
  case x :: xs1 => x + 1 :: incAll(xs1)
}

なお、上記処理は末尾再帰ではない（javaのループコードに置き換えられない）ため1つ1つの再帰呼び出しがスタックフレームを必要とするので、現状の仮想マシンのもとでは3万から5万程度までの要素数のリストにしか使えないみたいデス。残念(´・ω・｀)

ちなみにループを使って書き出すと下のような感じになりますが、とても効率が悪いです。

var result = List[Int]()
// 新しい要素を結果値のリストの末尾に追加しますが
// resultで表現されるリストの長さに比例する処理になるので
// リストの長さの自乗に比例する時間が必要です(´・ω・｀)
for(x <- xs)result = result ::: list(x + 1)
result

そんな感じの諸問題を解決するためにListBufferを使いましょう(｀・ω・´)。ListBufferではリスト要素をバッファーに蓄積していって、最終的にバッファーからリストへの変換を行うことで効率的にリストの組み立てを行うことが出来るみたいです。

それじゃ前述のincAllをListBufferを利用して書き換えてみますよ(｀・ω・´)

// ListBufferパッケージをインポートしますよ
import scala.collection.mutable.ListBuffer

// リストバッファーでの構築を開始します
val buf = new listBuffer[int]
// 各要素をインクリメントした値を末尾に追加していきます
for (x <- xs) buf += x + 1
// リストに変換を行ないます
buf.toList

こんなふうにListBufferを利用するのが効率のよいリストの構築方法みたいですｃ⌒っﾟдﾟ)っφ　ﾒﾓﾒﾓ...

Listクラスの実際の中身

前回はリストクラスを実際のものよりも簡易化した実装で表現してみていったのですが、いたるところで再帰を利用しているのでスタックオーバーフローを起こすという欠陥があるそうです。

ちなみに前回見ていったコードの一部はこんな感じですな(´・ω・｀)

 // 要素数はtailの要素数をベースに求めるみたいですね(´・ω・｀)
 // ...でもこれだけみてると再帰的に処理される風だなぁ...どうなんだろ？
def length:int = if(isEmpty) 0 else 1 + tail.length

// drop処理もtailで定義されるリストをベースに処理しますね
// これも再帰処理すなー
def drop(n:int):List[T] = 
  if(isEmpty) Nil
  else if(n <= 0) this
  else tail.drop(n - 1)

// mapもheadの値に関数適用するって処理を
// 再帰的に行なっていく感じですな
def map[U](f:T => U):List[U] =
  if(isEmpty) Nil
  else f(head) :: tail.map(f)

どれも末尾再帰になっていないのでincAllと同様に要素数が3~5万程度が限度になりそうです(´・ω・｀)

そんなわけで実際のListクラスのmapの実装を見てみますよ

// パラメータとして関数を渡しますね 
final override def map[U](f:T => U):List[U] = {
  // リストバッファーを利用します
  val b = new ListBuffer[U]
  // リストを一旦ミュータブルな変数に格納します
  var these = this
  // ループで先頭要素を編集してバッファーに追加しますよ
  while(!these.isEmpty){
    b += f(these.head)
    these = these.tail
  }
  // バッファー→リストへの変換です
  b.toList
}

ループを利用することで計算速度と同時にスケーラビリティも確保できるYO!とのことです。ちなみにtoListにかかる計算コストもリストの長さに比例するものではないので、まあいいんじゃない？という感じみたいですね。

toListの計算コスト

せっかくなのでtoListの計算コストを見てみますデス。まずはListBufferのコードを見ていきますよ。

// パッケージ宣言通りミュータブルなオブジェクトです
package scala.collection.immutable
final class ListBuffer[T] extends Buffer[T] {
  //// 3つの非公開フィールドを持ちます(ミュータブルですね) 
  // バッファーに格納される全ての要素のリストです
  private var start: List[T] = Nil
  // リストの最後の::セルを指します
  // Listのサブクラスである::が格納されますね
  private var last0: ::[T] = _
  // toListでの変換をしたかどうかを格納します
  private var exported: Boolean = false
  //...
  
  // 実際のtoListはこんな感じです
  verride def toList[T] = {
    // 変換結果をexportedに格納して
    exported = !start.isEmpty
    // リストを返します
    start
  }
}

ListBufferdでは内部的にリストを保持しており、toListの処理は単純にstartに格納されたリストを返すだけなので計算コストは殆どかかって無いのが分かりますね。

また、ListBuffer内のリストは値をバッファーに追加する+=メソッド内でリストのサブクラス::によって構築されるみたいです。ちなみにexportedの値はバッファへの要素の追加時に利用します。具体的には構築後のリストが更なる追加操作で書き換わらないように、新しくコピーしたリストオブジェクトを生成するみたいです。これによって既に参照済みの以前toListで構築したリストは維持されます。

override def += (x:T){
  // 既にリストが構築済みな場合は新しいオブジェクトをコピーして生成します
  if(exported) copy()
  // コピーしたもの（未構築の場合はオリジナルのもの）に要素を追加しますよ
  if(start.isEmpty){
    // 新しい::オブジェクトを生成します
    last0 = new scala.::(x, Nil)
    start = last0
  } else {
    val last1 = last0
    // 新しい::オブジェクトを生成します
    last0 = new scala.::(x,Nil)
    // リストのサブクラス::のtailの結果値を置き換えます
    last1.tl = last0
  }
}

通常はリスト構築後に要素の追加は発生しないはずなので、コピー動作もめったに行われない…はずですね…多分(´・ω・｀)

それとlistBufferの定義で散々でてきたListのサブクラスの::は、実際には下のように定義されます。実際の定義を見てみると::で返すtailの値はミュータブルであることが分かります。

// tailの結果値tlは実際にはvar定義になております
final case class ::[U](hd:U, private[scala] var tl:List[U]) extends list[U] {
  def head = hd
  def tail = tl
  override def isEmpty:Boolean = false
}


tailの結果値になるtlがvarで定義されていることでListBuffer等で計算コストを抑えることが出来ているみたいです。ただしprivate宣言にもあるとおりscalaパッケージ以外からのアクセスはできないようになっているので糧に書き換えられことは（多分）ないと思われます(´・ω・｀)

関数型の見かけ


ここまでリストの内部実装を見てきたわけですが、Scalaのリストは見た目は純粋な関数型のように振舞うにもかかわらず、内部的には命令型の実装になっているみたいです。これは計算効率をあげつつも、関数型としてのメリットを享受するためのようです。

ここでいう関数型としてのメリットは、例えばミュータブル変数の開放によるプログラムの脆弱性の防止なんかが当てはまるそうです。具体的な例としては、上記コードのように::によるリストの構築ではリストのtailを計算効率の向上のために再利用(共有)しているのですが、仮にListのtailをオープンにしてしますと次のようなコードで影響が出てしまいます。

scala> val xs = List(1,2,3,4,5)
xs: List[Int] = List(1, 2, 3, 4, 5)

scala> val ys = 1 :: xs
ys: List[Int] = List(1, 1, 2, 3, 4, 5)

scala> val zs = 2 :: ys
zs: List[Int] = List(2, 1, 1, 2, 3, 4, 5)
 
// Scalaではできない操作ですが(´・ω・｀)
// ysリストを先頭2要素だけに縮小します
ys.drop(2).tail = Nil
// 結果的に複数の値の内容が書き換わってしまいます。
ys: List[Int] = List(1, 1)
zs: List[Int] = List(2, 1, 1)

純粋関数型ふうの実装をやめた結果としてオープンな共有範囲が広がってしまうと何がしかの変更の影響範囲が大きくなってしまうので、Scalaのリストでは内部的にはミュータブルでも外からみたらイミュータブルという実装になっているそうです。ちなみにjavaのStringBufferも同じようなポリシーだとか(´・ω・｀)

ここらへんはイミュータブル⇔ミュータブルの境界線的な参考になるなぁと思います。どのあたりでミュータブルに切り替えたらイイの？とかの基準になりそうだなぁと…

以上ー

22章ではScalaのリストについてのアレやコレをやりましたよー、若干写経気味だったけどもイミュータブルとミュータブルの使い分け例みたいな感じで読めて面白かったです。

次回は23章のfor式再説に入っていきますねー、あと十章くらい？が、頑張ります(´・ω・｀)