List foldLeft implementations
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
object C extends App { | |
def time[F](f: => F) = { | |
val t0 = System.nanoTime | |
val ans = f | |
printf("Elapsed: %.3f\n",1e-9*(System.nanoTime-t0)) | |
ans | |
} | |
def lots[F](n: Int, f: => F): F = if (n <= 1) f else { f; lots(n-1,f) } | |
def bench[F](what:String, n:Int, f: => F) = { | |
println(what + ": warming...") | |
lots(n, f) | |
time(what, f) | |
} | |
def foldLeft[A, B](list: List[A], z: B)(f: (B, A) => B): B = { | |
var acc = z | |
var these = list | |
while (!these.isEmpty) { | |
acc = f(acc, these.head) | |
these = these.tail | |
} | |
acc | |
} | |
@annotation.tailrec | |
def foldLeft2[T,U](list: List[T], acc: U)(f: (T, U) => U): U = { | |
list match { | |
case x :: xs => foldLeft2(xs, f(x, acc))(f) | |
case Nil => acc | |
} | |
} | |
@annotation.tailrec | |
final def foldLeft3[T, U](list: List[T], acc: U)(f: (T, U) => U): | |
U = if (list eq Nil) acc else foldLeft3(list.tail, f(list.head, acc))(f) | |
val size = 500000 | |
val list = List.fill(size)(1) | |
val warm = 20 | |
val n = 2 | |
val f = (a:Int, b:Int) => a * b | |
bench("tailrec match foldLeft2", warm, lots(n, foldLeft2(list, 0)(f))) | |
bench("tailrec if/else foldLeft3", warm, lots(n, foldLeft3(list, 0)(f))) | |
bench("lib foldLeft", warm, lots(n, list.foldLeft(0)(f))) | |
bench("pulled-in foldLeft", warm, lots(n, foldLeft(list, 0)(f))) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Timings on 2.9.1 compiled with -optimized (ran under sbt) are:
[info] Running C
tailrec match foldLeft2: warming...
Elapsed: 0.024
tailrec if/else foldLeft3: warming...
Elapsed: 0.045
lib foldLeft: warming...
Elapsed: 0.068
pulled-in foldLeft: warming...
Elapsed: 0.069