Scala初学者のためのテクニック集（Memoization）

Scala初学者のためのテクニック集、今回は Memoization を紹介します。

メモ化（英: Memoization）とは、プログラムの高速化のための最適化技法の一種であり、サブルーチン呼び出しの結果を後で再利用するために保持し、そのサブルーチン（関数）の呼び出し毎の再計算を防ぐ手法である。メモ化は構文解析などでも使われる（必ずしも高速化のためだけとは限らない）。キャッシュはより広範な用語であり、メモ化はキャッシュの限定的な形態を指す用語である。分割統治法とメモ化の両方を利用したものを動的計画法と呼ぶ。（Wikipediaより）
https://ja.wikipedia.org/wiki/%E3%83%A1%E3%83%A2%E5%8C%96

Memoization（日本語だと「メモ化」）は、言語に関係なく一般的なプログラミングのテクニックですが、今回はScalaのMemoizationについて考えてみたいと思います。

Memoizationの具体例

解決したいこと

例えば以下のような、編集にとても時間のかかる処理が色んな場所から何度も呼び出されるケースを考えてみます。

object Utility {
  def edit(value: String): String = {
    println(s"とても遅い編集処理を実行中 : $value")
    Thread.sleep(3000)
    value + "（編集）"
  }
}

object Example {
  def main(args: Array[String]) = {
    // 例では一箇所からしか呼び出していないが、
    // 実際には色んな場所から呼び出しているとする
    val start = System.currentTimeMillis
    println(Utility.edit("Tokyo"))
    println(Utility.edit("Kanagawa"))
    println(Utility.edit("Tokyo"))
    println(Utility.edit("Chiba"))
    println(Utility.edit("Kanagawa"))
    println("Elapsed time: %1d ms: ".format(System.currentTimeMillis - start))
  }
}

これを実行すると、以下の通り呼び出す度に遅い編集処理が走ってしまうため処理に時間がかかってしまいます。

とても遅い編集処理を実行中 : Tokyo
Tokyo（編集）
とても遅い編集処理を実行中 : Kanagawa
Kanagawa（編集）
とても遅い編集処理を実行中 : Tokyo
Tokyo（編集）
とても遅い編集処理を実行中 : Chiba
Chiba（編集）
とても遅い編集処理を実行中 : Kanagawa
Kanagawa（編集）
Elapsed time: 15529 ms: 

Process finished with exit code 0

例えばこれを何百回も呼び出す必要がある場合、一度処理したものは再利用できるようにしておきたいものです。今回はこれをMemoizationで実現してみましょう。

Memoizationの適用

まずは、 Memoizer トレイトに抽象化したMemoizaitonの実装を準備をしておきます。

trait Memoizer {
  def memo[X, Y](f: X => Y): (X => Y) = {
    val cache = scala.collection.mutable.Map[X, Y]()
    (x: X) => cache.getOrElseUpdate(x, f(x))
  }
}

memo メソッドは、引数に X を受け取って Y を返す関数（f: X => Y）を受け取り、X を受け取って Y を返す関数（(X => Y)）を返します。

内部の処理では、まずmutableなMapでキャッシュを定義し、返却値の型の (X => Y) から推論したキー (x: X) を受け取り、キーが存在すればその値を、キーが存在しなければキャッシュに追加したうえでその値を返却する関数を返却しています。

それでは、先程作成した　Memoizer トレイトを Utility クラスに適用してみましょう。

object Utility extends Memoizer {
  def edit(value: String): String = {
    println(s"とても遅い編集処理を実行中 : $value")
    Thread.sleep(3000)
    value + "（編集）"
  }
  
  // メモ化
  val memoEdit = memo(edit)
}

ここでは、edit メソッドをメモ化する memoEdit を定義しました。

それでは使ってみましょう。
呼び出し部分を以下の通り修正します。

object Example {
  def main(args: Array[String]) = {
    val start = System.currentTimeMillis
    println(Utility.memoEdit("Tokyo"))
    println(Utility.memoEdit("Kanagawa"))
    println(Utility.memoEdit("Tokyo"))
    println(Utility.memoEdit("Chiba"))
    println(Utility.memoEdit("Kanagawa"))
    println("Elapsed time: %1d ms: ".format(System.currentTimeMillis - start))
  }
}

実行した結果が以下になります。

とても遅い編集処理を実行中 : Tokyo
Tokyo（編集）
とても遅い編集処理を実行中 : Kanagawa
Kanagawa（編集）
Tokyo（編集）
とても遅い編集処理を実行中 : Chiba
Chiba（編集）
Kanagawa（編集）
Elapsed time: 9318 ms: 

Process finished with exit code 0

この通り一度実行した引数に対する結果はキャッシュされるので、処理時間が短縮しました。

Scalaz.memoを使用する

なお、先の例ではMemoizationの仕組みを自前で実装しましたが、
Scalaz で提供されているmemoを使用するとその必要はなくなります。

build.sbtに以下を追加してください。

libraryDependencies += "org.scalaz" %% "scalaz-core" % "7.2.7"

Utility にscalazのMemoを使って scalazMemoEdit を定義します。

object Utility {
  def edit(value: String): String = {
    println(s"とても遅い編集処理を実行中 : $value")
    Thread.sleep(3000)
    value + "（編集）"
  }

  val scalazMemoEdit: String => String = scalaz.Memo.mutableHashMapMemo(edit)

}

使ってみましょう！

object Example {
  def main(args: Array[String]) = {
    // 例では一箇所からしか呼び出していないが、
    // 実際には色んな場所から呼び出しているとする
    val start = System.currentTimeMillis
    println(Utility.scalazMemoEdit("Tokyo"))
    println(Utility.scalazMemoEdit("Kanagawa"))
    println(Utility.scalazMemoEdit("Tokyo"))
    println(Utility.scalazMemoEdit("Chiba"))
    println(Utility.scalazMemoEdit("Kanagawa"))
    println("Elapsed time: %1d ms: ".format(System.currentTimeMillis - start))
  }
}

実行結果

とても遅い編集処理を実行中 : Tokyo
Tokyo（編集）
とても遅い編集処理を実行中 : Kanagawa
Kanagawa（編集）
Tokyo（編集）
とても遅い編集処理を実行中 : Chiba
Chiba（編集）
Kanagawa（編集）
Elapsed time: 9313 ms: 

Process finished with exit code 0

さっきと同じように処理時間が短縮されましたね。

というわけで、今回はMemoizationでした。

参考文献

• "Scala Design Patterns" - Packt Publishing