Skip to content

Instantly share code, notes, and snippets.

@akirillov
Last active July 6, 2016 15:34
Show Gist options
  • Save akirillov/82934739b9df131a1a602c9b46961a75 to your computer and use it in GitHub Desktop.
Save akirillov/82934739b9df131a1a602c9b46961a75 to your computer and use it in GitHub Desktop.
Comparison of tail recursive and imperative way of `map` implementation
/*
Test: tail recursive map vs imperative map
*/
object TailrecTest extends App{
def measure[A](f: => A): (A, Long) = {
val start = System.currentTimeMillis()
(f, System.currentTimeMillis() - start)
}
/*
Test: tail recursive map vs imperative map
*/
def mapF[T,U](xs: List[T])(f: T => U): List[U] = {
@tailrec
def mapr(ys: List[T], acc: List[U]): List[U] = ys match {
case Nil => acc
case z :: zs => mapr(zs, f(z) :: acc)
}
mapr(xs, List()).reverse
}
def mapI[T,U](xs: List[T])(f: T => U): List[U] = {
val listBuffer = ListBuffer.empty[U]
var rest = xs
while (rest.nonEmpty) {
listBuffer.append(f(rest.head))
rest = rest.tail
}
listBuffer.toList
}
val sample = List.fill(1000000)(2)
(1 to 1000) foreach { _ =>
val native = measure( sample map (_.toString))
val fr = measure(mapF(sample)(_.toString))
val ir = measure(mapI(sample)(_.toString))
println(s"native: ${native._2}")
println(s" rec: ${fr._2}")
println(s" iter: ${ir._2}")
println("--")
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment