Skip to content

Instantly share code, notes, and snippets.

@baskakov
Created January 15, 2014 14:34
Show Gist options
  • Save baskakov/8437349 to your computer and use it in GitHub Desktop.
Save baskakov/8437349 to your computer and use it in GitHub Desktop.
Sum by keys
def avgTime(message: String, f: => Any) {
var avg = 0L
val c = 42
1 to c foreach {
_ =>
val t0 = System.nanoTime()
f
val t1 = System.nanoTime()
avg += t1 - t0
}
println(message + " avg time is " + (avg/c/1000000) + " ms")
}
def sumByKeys[A](tuples: List[(A, Long)]) = {
tuples.groupBy(_._1).mapValues(_.map(_._2).sum)
}
import annotation.tailrec
@tailrec
final def tailSum[A](tuples: List[(A, Long)], acc: Map[A, Long] = Map.empty[A, Long]): Map[A, Long] = tuples match {
case (k, v) :: tail => tailSum(tail, acc + (k -> (v + acc.get(k).getOrElse(0L))))
case Nil => acc
}
def foldLeftSum[A](tuples: List[(A, Long)]) = tuples.foldLeft(Map.empty[A, Long])({
case (acc, (k, v)) => acc + (k -> (v + acc.get(k).getOrElse(0L)))
})
def mutableSum[A](tuples: List[(A, Long)]) = {
val m = scala.collection.mutable.Map.empty[A, Long].withDefault(_ => 0L)
for ((k, v) <- tuples) m += (k -> (v + m(k)))
m
}
val tuples = (0L to 42000L).map(l => l % 10 -> l).toList
avgTime("default", sumByKeys(tuples))
avgTime("tailrec", tailSum(tuples))
avgTime("foldleft", foldLeftSum(tuples))
avgTime("mutableSum", mutableSum(tuples))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment