コップ本２の１９章「型のパラメータ化」をやってみる。その１

Scala 勉強

「関数型待ち行列」をつくる、という題材を通して型のパラメータ化を学ぶ章です。関数型待ち行列の要件は

１．head：待ち行列の先頭要素を返す
２．tail：先頭要素を取り除いた形で待ち行列を返す
３．enqueue：指定した要素を末尾に追加した新しい待ち行列を返す

scala> val q = Queue(1,2,3)
q: Queue[Int] = Queue(1,2,3)

scala> val q1 = q enqueue 4
q1: Queue[Int] = Queue(1,2,3,4)

scala> q
res0: Queue[Int] = Queue(1,2,3)

とenqueue操作は元のqには影響を与えない。という動きだそうだ。


早速単純な実装が提示されている。SlowAppendQueueはenqueueが遅く、SlowHeadQueueはHeadが遅い、という欠点がある。

class SlowAppendQueue[T](elems: List[T]) {
  def head = elems.head
  def tail = new SlowAppendQueue(elems.tail)
  def enqueue(x: T) = new SlowAppendQueue(elems ::: List(x))
  override def toString:String = elems.toString
}

class SlowHeadQueue[T](smele: List[T] {
  def head = smele.last
  def tail = new SlowHeadQueue(smele.init)
  def enqueue(x: T) = new SlowHeadQueue(x :: smele)
  override def toString:String = smele.toString
}


初期値に０〜１００までの101要素のリストを渡し、どれくらい速度に違いがあるのか、こんな関数を作って調べてみた。

def count[U](f: => U): Unit = {
  val now = System.nanoTime
  val res = f
  val etime = (System.nanoTime - now) / 1000.0
  println(elapsed time = " + etime + "(ms) : " + res)
}


SlowAppendQueue case:
head = 58.257(ms)
tail = 16.903(ms)
enqueue = 1281.638(ms)


SlowHeadQueue case:
head = 40.749(ms)
tail = 795.666(ms)
enqueue = 11.772(ms)


SlowAppendQueueは予想通りenqueueが強烈に遅い。SlowHeadはheadよりもinitを使うtailが遅い。Scalaのバージョンのせいかもしれない。深くは突っ込まないでおこう。つまりは、操作によってパフォーマンスが遅いよ、という実装はあんまりよくないということを伝えたいのである。


で次に出てくる実装が、SlowAppendとSlowHeadのいいとこ取りをした実装である。

class Queue[T](
  private val leading: List[T],
  private val trailing: List[T]
  )
{
  private def mirror = if (leading.isEmpty) 
                          new Queue(trailing.reverse, Nil)
                       else 
                          this
  def head = mirror.leading.head
  def tail = {
      val q = mirror
      new Queue(q.leading.tail, q.trailing)
    }
  def enqueue(x: T) = new Queue(leading, x :: trailing)
}


こんな感じで使う。

val q = Queue((0 to 100).toList, Nil)


結果は以下のように大変理想的なものとなった。


Queue case:
head = 16.903(ms)
tail = 12.98(ms)
enqueue = 13.282(ms)


当然といえば当然だ。enqueue用に二つのリストを扱えるようにしてるのだから。リスト全体を取ってくるときに「leading ::: trailing.reverse」とするのが遅くなりそうなので、toStringをoverrideしてSlowAppend、SlowHeadと比較してみる。


SlowAppend.toString = 35(ms)
SlowHead.toString = 63(ms)
Queue.toString = 34(ms)


なぜかListを単純に出力するのよりも早い。(0 to 50)、(51 to 100).reverse の二つに分けて見ても、75msとそれほど遅くない。


教本によると、この実装は複雑さを利用者に見せているのでよろしくないそうです。確かに元のリストを分けて、反対側は逆順に並べる、というのは使いにくい。ということで、まずは基本コンストラクターをprivateにして隠す。

class Queue[T] private (
  private val leading: List[T],
  private val trailing: List[T]
  )


こうするとQueueクラスを作れなくなるので、補助コンストラクタを作る。

class Queue[T] private (
  private val leading: List[T],
  private val trailing: List[T]
  )
{
  def this() = this(Nil, Nil)
  def this(elems: T*) = this(elems.toList, Nil)


でもエラーがでる。

error: ambiguous reference to overloaded definition,
both constructor Queue in class Queue of type (elems: T*)this.Queue[T]
and  constructor Queue in class Queue of type (leading: List[T], trailing: List[T])this.Queue[T]
match argument types (List[T],scala.collection.immutable.Nil.type)
                          new Queue(trailing.reverse, Nil)
                          ^


ちょっと悩んだが、T*をList[T]に変えたら動いた。T*だと、List[Int]、List[Int]もT*に含まれるから、Queue(trailing.reverse, Nil)を行うときに基本コンストラクターと補助コンストラクタのどっちを呼べばいいの？　となるのは納得です。


明日以降は、非公開クラスというのを使った実装に移る。