Fibonacci Test

FibTest.scala

import scala.collection.mutable

/**
  * Created by okayayohei on 2017/03/11.
  */
object Main {

  trait Fib {
    def fib(n: Long): Long
  }

  object Normal extends Fib {
    def fib(n: Long): Long = {
      if(n <= 2) 1
      else fib(n - 1) + fib(n - 2)
    }
  }

  object CallOnce extends Fib {
    def fibLocal(a: Long, b: Long, c: Long): Long = {
      if(c <= 2) a
      else fibLocal(a + b, a, c - 1)
    }
    def fib(n: Long) = {
      fibLocal(1, 1, n)
    }
  }

  object Cache extends Fib {
    var cache: mutable.Map[Long, Long] = scala.collection.mutable.Map.empty[Long, Long]
    def fib(n: Long) = {
      cache.getOrElseUpdate(n, {
        if(n <= 2) 1
        else fib(n - 1) + fib(n - 2)
      })
    }
  }

  object CacheAndCallOnce extends Fib {
    var cache: mutable.Map[Long, Long] = scala.collection.mutable.Map.empty[Long, Long]
    def fibLocal(a: Long, b: Long, c: Long): Long = {
      if(c <= 2) a
      else fibLocal(a + b, a, c - 1)
    }
    def fib(n: Long) = {
      cache.getOrElseUpdate(n, {
        fibLocal(1, 1, n)
      })
    }
  }

  def main(args: Array[String]): Unit = {

    val n: Long = 50

    printExecutionTime {
      println("----Normal----")
      println(Normal.fib(n))
    }

    printExecutionTime {
      println("----CallOnce----")
      println(CallOnce.fib(n))
    }

    printExecutionTime {
      println("----Cache----")
      println(Cache.fib(n))
    }

    printExecutionTime {
      println("----Cache----")
      println(Cache.fib(n))
    }

    printExecutionTime {
      println("----CacheAndCallOnce----")
      println(CacheAndCallOnce.fib(n))
    }

    printExecutionTime {
      println("----CacheAndCallOnce----")
      println(CacheAndCallOnce.fib(n))
    }
  }

  /** 引数の処理の実行時間を表示 */
  def printExecutionTime(proc: => Unit) = {
    val start = System.currentTimeMillis
    proc
    println((System.currentTimeMillis - start) + "msec")
  }

}

[info] Running Main 
----Normal----
12586269025
55601msec
----CallOnce----
12586269025
15msec
----Cache----
12586269025
37msec
----Cache----
12586269025
0msec
----CacheAndCallOnce----
12586269025
3msec
----CacheAndCallOnce----
12586269025
0msec
[success] Total time: 63 s, completed 2017/03/11 11:55:16