Scalaを使ってみる: (10) immutable MultiSetのメソッドを高速化する (続き)

Scalaを勉強している．勉強中の身ではあるが，以下を例題として，Scalaプログラムの作り方について説明してみる．

テキストファイル中に現れる英単語の出現回数を数えて，出現回数の多い語から表示する．

入力のテキストファイルとしては，Project Gutenberg 中のHalmet を用いる(ファイル名を hamlet.txt，改行はLFにした)．
なお利用している環境は，Ubuntu 8.04 LTS上の Scala 2.8.0 RC2 (2010年5月10日リリース)， Java 1.6.0である．

リンク

高速化の続き

今回は，良く利用する filter, map 等について，効率的な実装に書き換えてみる．

filter と filterNot メソッド

filter も intersect 等と同様に， mutable な Map に登録したのち toMap で immutable な Map に変換し，マルチ集合を作ることにする．

  override def filter(p: A => Boolean) = {
    val m = collection.mutable.Map[A,Int]()
    for (x <- keys if p(x))
      m += x -> this(x)
    new MS(m.toMap)
  }

filterNot は filter の否定だ．

  override def filterNot(p: A => Boolean) = filter(! p(_))

map と collect メソッド

map も filter と同様に処理するが， Map にすでに登録されている可能性があるので，要素数を合計するように書く．

  def map[B](f: A => B): MS[B] = {
    val m = collection.mutable.Map[B,Int]()
    for (x <- keys) {
      val y = f(x)
      m += y -> (m.getOrElse(y,0)+this(x))
    }
    new MS(m.toMap)
  }

collect も map と同様だ．

  def collect[B](pf: PartialFunction[A,B]): MS[B] = {
    val m = collection.mutable.Map[B,Int]()
    for (x <- keys if pf.isDefinedAt(x)) {
      val y = pf(x)
      m += y -> (m.getOrElse(y,0)+this(x))
    }
    new MS(m.toMap)
  }

flatMap と flatten メソッド

flatMap は以下のようになる．

  def flatMap[B](f: A => Traversable[B]): MS[B] = {
    val m = collection.mutable.Map[B,Int]()
    for (x <- keys; y <- f(x))
      m += y -> (m.getOrElse(y,0)+this(x))
    new MS(m.toMap)
  }

flatten は flatMap と同様だ．

  override def flatten[B](implicit asTraversable: A => Traversable[B]): MS[B] = {
    val m = collection.mutable.Map[B,Int]()
    for (x <- keys; y <- asTraversable(x))
      m += y -> (m.getOrElse(y,0)+this(x))
    new MS(m.toMap)
  }