Skip to content

Instantly share code, notes, and snippets.

@halcat0x15a
Created December 18, 2011 06:03
Show Gist options
  • Save halcat0x15a/1492524 to your computer and use it in GitHub Desktop.
Save halcat0x15a/1492524 to your computer and use it in GitHub Desktop.
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
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
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
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment