Memo

Memo

メモ化！

恒例のフィボナッチ数列を書いてみる。

	scala> def time[A](f: => A): A = {
	| val s = System.nanoTime
	| val x = f
	| val e = System.nanoTime
	| (((e - s) / 1000).toDouble / 1000000).println
	| x
	| }
	time: [A](f: => A)A
	scala> object Fib {
	| def unapply(n: Long): Option[Long] = (n >= 2).option(n - 2)
	| }
	defined module Fib
	scala> lazy val fib: Long => Long = {
	| case 0 => 0
	| case 1 => 1
	| case Fib(n) => fib(n) + fib(n + 1)
	| }
	fib: Long => Long = <lazy>
	scala> time(fib(40))
	4.055657
	res6: Long = 102334155
	scala> time(fib(43))
	16.81403
	res7: Long = 433494437

view raw memo1.scala hosted with ❤ by GitHub

メモ化してみる。

	scala> implicit lazy val m = immutableHashMapMemo[Long, Long]
	m: scalaz.Memo[Long,Long] = <lazy>
	scala> val memofib = m(fib)
	memofib: Long => Long = <function1>
	scala> val memofib = !fib
	memofib: Long => Long = <function1>
	scala> time(memofib(40))
	4.034974
	res8: Long = 102334155
	scala> time(memofib(40))
	2.8E-5
	res9: Long = 102334155
	scala> time(memofib(43))
	16.980203
	res10: Long = 433494437
	scala> time(memofib(43))
	2.5E-5
	res11: Long = 433494437

view raw memo2.scala hosted with ❤ by GitHub

m(fib)はMemo#applyが呼ばれ、メモ化された関数が返ります。
!fibはFunction1Wに暗黙の型変換され、unary_!が呼ばれています。
unary_!は暗黙のパラメータでMemoをとり、メモ化します。

実装をメモ化する。

	scala> implicit lazy val m = mutableHashMapMemo[Long, Long]
	m: scalaz.Memo[Long,Long] = <lazy>
	scala> lazy val mfib: Long => Long = m {
	| case 0 => 0
	| case 1 => 1
	| case Fib(n) => mfib(n) + mfib(n + 1)
	| }
	mfib: Long => Long = <lazy>
	scala> time(mfib(43))
	0.002366
	res13: Long = 433494437
	scala> time(mfib(50))
	1.23E-4
	res14: Long = 12586269025

view raw memo3.scala hosted with ❤ by GitHub

Memoには標準でいくつかの実装が用意されおり、Memosに定義されています。

memo関数により自分で定義することもできます。

	scala> val optionMemo = memo[Int, Int] { f =>
	| var o = none[(Int, Int)]
	| k => {
	| o some {
	| case (kk, vv) => (kk === k).fold(vv, f(k))
	| } none {
	| val v = f(k)
	| o = (k, v).some
	| v
	| }
	| }
	| }
	optionMemo: scalaz.Memo[Int,Int] = scalaz.Memos$$anon$3@1dd8a94
	scala> val f = optionMemo { i =>
	| Thread.sleep(1000)
	| i |+| 100
	| }
	f: Int => Int = <function1>
	scala> time(f(10))
	1.002767
	res44: Int = 110
	scala> time(f(10))
	0.001382
	res45: Int = 110
	scala> time(f(11))
	1.000204
	res46: Int = 111

view raw memo4.scala hosted with ❤ by GitHub