fork download
copy 
  1. import scala.math.pow
  2.  
  3. sealed trait TailRec[A] {
  4.   final def run : A = this match {
  5.     case Return(v)  => v
  6.     case Suspend(k) => k().run
  7.   }
  8. }
  9.  
  10. case class Return[A](v : A) extends TailRec[A]
  11. case class Suspend[A](resume : () => TailRec[A]) extends TailRec[A]
  12.  
  13. object Main {
  14.   def normal (n : Int) : Int =
  15.     if (n == 0) 0
  16.     else 1 + normal(n - 1)
  17.  
  18.   def cps (n : Int) : Int = {
  19.     def loop (i : Int, k : Int => TailRec[Int]) : TailRec[Int] =
  20.       if (i == 0) k(0)
  21.       else loop(i - 1, x => Suspend(() => k(1 + x)))
  22.  
  23.     loop(n, t => Return(t)).run
  24.   }
  25.  
  26.   def accum (n : Int) : Int = {
  27.     def loop (i : Int, a : Int) : Int =
  28.       if (i == 0) a
  29.       else loop(i - 1, a + 1)
  30.  
  31.     loop(n, 0)
  32.   }
  33.  
  34.   def main(args : Array[String]) : Unit = {
  35.     def getTime[A] (f : A => Any, i : A, n : Int) : Double = {
  36.       val s = System.currentTimeMillis()
  37.       for (_ <- 1 to n)
  38.         f(i)
  39.  
  40.       (System.currentTimeMillis() - s).toDouble / n.toDouble
  41.     }
  42.  
  43.     for (i <- 2 to 7)
  44.       print(s"${getTime(accum, pow(10, i).toInt, 10)},")
  45.  
  46.     println()
  47.  
  48.     for (i <- 2 to 7)
  49.       print(s"${getTime(cps, pow(10, i).toInt, 10)},")
  50.   }
  51. }
Time limit exceeded #stdin #stdout 5s 358464KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0.0,0.1,0.0,0.3,2.6,13.1,
0.5,0.5,0.9,17.7,242.7,
https://ideone.com/7lkBdU
language:
Scala (scala 2.12.8)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!