Sum by keys

gistfile1.txt

  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))