A benchmark to compare different algorithms with increasing sample size

Benchcoat.scala

/**
   Benchcoat.scala 
      2011-10-22 v.2: Improvement in plot-code and renaming prettyPrint

   extend Benchcoat by 
   providing a List of (
     names, 
     combined with a functions, which takes some 
       I and returns some O
   )
   typical Types for I,O are List[Int] for both, or Seq[Double], but very long Strings would
   make sense too, and I and O don't need to be of the same Kind (else they were I and I).
*/
abstract class Benchcoat [I, O]{
  /**
     abstract methods, need implementation in your class.
     Most important: provide a List of names, combined to functions you like to compare.
  */
  val list2bench: List[(String, I => O)]
  // typical case: Generate a List of n random Values of type I
  def iGenerator (n: Int) : I 
  /* typical case: list.take (n)
     used to protocoll the increasing cost of increasing n
  */
  def takePart (i: I, n: Int) : I 

  val r = util.Random 
  import collection.mutable.ListBuffer
  var buf = ListBuffer [String] ()
  
  def timed (xs: I) (f: I => O) = {
    val a = System.currentTimeMillis 
    val res = f (xs)
    val z = System.currentTimeMillis 
    val delta = z-a
    val s = "" + (delta / 1000.0)
    println (s)
    buf += s
    res
  }

  def main (args: Array [String]) : Unit = {
    val n = args(0).toInt  
    val xs = iGenerator (n) 
    /* 
       With 1 Mio. as param, start it with 100 000, 200k, 300k, ... 1Mio. cases.
         a) warmup
         b) look, where the process gets linear to size
    */
    list2bench.foreach (f => {
      buf += f._1 // name
      println (f._1)
      (1 to 10) foreach (i => {
        val res = timed (takePart (xs, n/10 * i)) (f._2)
        compat.Platform.collectGarbage
      });
    println ()}
    )
    println (toPrettyString)
    // Be aware, that in each run, existing files are silently overwritten.    
    // if uncommented in bench.plot, this will be true for benchplot.png as well.
    s2File (toPrettyString, "bench.data")
    s2File (gnuplotPrint, "bench.plot")
  }
  
  def s2File (s: String, filename: String) {
    val f = new java.io.File (filename)
    val out = new java.io.PrintWriter (f)
    try { out.print (s) }
    finally { out.close }
  }

  def toPrettyString : String = {
    /* yes, fixed number of iterations to 10
       +1 for the headlines=11 */
    val width = buf.size / 11  
    val sb = new StringBuffer 
    for (row <- (0 to 10)) {
      sb.append (row + " \t") 
      for (col <- (0 to width - 1))
        sb.append (buf (col * 11 + row) + " \t") 
      sb.append ("\n")
    }
    sb.toString 
  }
  
  def prettyPrint = {
    /* yes, fixed number of iterations to 10
       +1 for the headlines=11 */
    val width = buf.size / 11  
    for (row <- (0 to 10)) {
      print (row + " \t") 
      for (col <- (0 to width - 1))
        print (buf (col * 11 + row) + " \t") 
      println ()
    }
  }
  
  /**
     usage: $dir > gnuplot 
            > load "bench.dat"
     Be aware, that in each run, existing files are silently overwritten.
  */
  def gnuplotPrint = {
    val cmd = """# set terminal png transparent nocrop enhanced font arial 8 size 420,320 
# set output 'benchplot.png'
set style data linespoints
set xtics border in scale 1,0.5 nomirror offset character 0, 0, 0 
set title "performance comparision v0.3" 
plot 'bench.data' using 2:xtic(1) t 2""" 
    val ext = for (i <- 2 to list2bench.size) yield "'' u " + (i+1) + " t " + (i+1)
    cmd + ext.mkString (", ", ", ", " ") + "\n"
  }
}

/**
  Sample usage, see 
  http://stackoverflow.com/q/7084212/312172
*/
object Li2LiBench extends Benchcoat [List[Int], List[Int]] {

  def iGenerator (n: Int) = (for (x <- 1 to n) yield r.nextInt (n)).toList 
  def takePart (li: List[Int], n: Int) = li.take (n) 
  
  def adrian1 (xs: List[Int]): List[Int] = {
    val maxIndex = xs.indexOf (xs.max)
    xs.take (maxIndex) ::: xs.drop (maxIndex + 1)
  }

  import collection.mutable._
      
  def adrian2(xs: List[Int]) = {
    var res = ArrayBuffer[Int] ()
    var max = xs.head
    var first = true;
    for (x <- xs) {
      if (first) {
        first = false;
        } else {
        if (x > max) {
          res.append(max)
          max = x
        } else res.append(x)
      }
    }
    res.toList
  }

  def daniel1 (xs: List[Int]): List[Int] = {
    val res = xs.splitAt (xs.indexOf(xs.max))
    res._1 ::: res._2.tail 
  }

  def daniel2 (xs: List[Int]): List[Int] = {
    var res = ListBuffer[Int]()
    var max = xs.head
    var first = true;   
    for (x <- xs) {
      if (first) {
        first = false;
      } else {
        if (x > max) {
          res += max
          max = x
        } else res += x
      }
    }
    res.toList
  }

  def soc1 (xs: List[Int]) = {
    val buf = xs.toBuffer
    buf -= (buf.max)
    buf.toList
  }

  def soc2 (xs: List[Int]) = {
    var max = xs.head
    for ( x <- xs.tail ) 
    yield {
      if (x > max) { val result = max; max = x; result}
      else x
    }
  }

  def paradigmatic1 (xs: List[Int]) = {
    def rec (max: Int, rest: List[Int], result: List[Int]): List[Int] = {
      if (rest.isEmpty) result
      else if (rest.head > max) rec (rest.head, rest.tail, max :: result)
        else rec (max, rest.tail, rest.head :: result)
    }
    rec (xs.head, xs.tail, List())
  }

  def paradigmatic2 (xs: List[Int]) = {
    val result = xs.tail.foldLeft( xs.head -> List[Int]() ) {
      (acc,x) =>
        val (max,res) = acc
        if( x > max ) x -> ( max :: res )
          else max -> ( x :: res )
    }
    result._2
  }

  import annotation.tailrec 
  @tailrec
  def uu2 (xs: List [Int], carry: List [Int]) : List [Int] = xs match {                                  
    case a :: b :: xs => if (a < b) uu2 (b :: xs, a :: carry) else uu2 (a :: xs, b :: carry) 
    case x :: Nil => carry 
    case Nil => Nil 
  }
  def sample2 (xs: List [Int]) : List [Int] =  uu2 (xs, List.empty)

  def sample3 (xs: List [Int]) : List [Int] =
    ((Nil : List[Int], xs(0)) /: xs.tail) ((p, x)=> if (p._2 > x) (x :: p._1, p._2) else ((p._2 :: p._1), x))._1

  val list2bench: List [(String, List[Int] => List[Int])] = List (
//      "adr1" -> adrian1 _,
      "adr2" -> adrian2 _,
      "dan1" -> daniel1 _,
      "dan2" -> daniel2 _,
      "soc1" -> soc1 _,
      "soc2" -> soc2 _,
      "para1" -> paradigmatic1 _,
      "para2" -> paradigmatic2 _,
      "takedrp" -> adrian1 _, 
      "@trmtch" -> sample2 _, 
      "foldL/:" -> sample3 _
  )
}

bench.data (tab-indentation doesn't look nice on the web): 0 adr2 dan1 dan2 soc1 soc2 para1 para2 takedrp @trmtch foldL/: 1 0.149 0.073 0.013 0.037 0.037 0.026 0.036 0.028 0.023 0.018 2 0.043 0.055 0.01 0.035 0.022 0.014 0.016 0.03 0.016 0.016 3 0.093 0.048 0.018 0.066 0.022 0.01 0.025 0.061 0.014 0.041 4 0.119 0.061 0.019 0.081 0.048 0.02 0.11 0.055 0.027 0.034 5 0.187 0.106 0.025 0.106 0.036 0.05 0.125 0.115 0.024 0.053 6 0.208 0.134 0.033 0.115 0.053 0.023 0.243 0.115 0.134 0.145 7 0.222 0.113 0.039 0.131 0.051 0.056 0.155 0.129 0.134 0.19 8 0.243 0.114 0.062 0.15 0.056 0.031 0.229 0.135 0.161 0.168 9 0.412 0.122 0.064 0.158 0.086 0.034 0.25 0.135 0.165 0.201 10 0.258 0.124 0.151 0.184 0.174 0.131 0.197 0.133 0.089 0.147

bench.plot set style data linespoints set xtics border in scale 1,0.5 nomirror offset character 0, 0, 0 set title "performance comparision" plot 'bench.data' using 2:xtic(1) t 2, '' u 3 t 3, '' u 4 t 4, '' u 5 t 5, '' u 6 t 6, '' u 7 t 7, '' u 8 t 8, '' u 9 t 9, '' u 10 t 10