Benchcoat.scala

/**
   Benchcoat.scala 
    done:
      2011-11-17 v.4: improvement in plot-code
        x-axis and y-axis needs description (how many units measured, time in second)
      2011-11-17 v.3: minor improvement in plot-code      
      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]{
  // define a name by overriding, to be used for output-files
  val name : String
  /**
     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.
    string2File (toPrettyString, "bench.data")
    string2File (gnuplotPrint (n), "bench.plot")
  }
  
  def string2File (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: cat bench.plot | gnuplot 
     Be aware, that in each run, existing files are silently overwritten.
  */
  def gnuplotPrint (problemsize: Int) = {
  /**
     transform the size to readable form: 
       1-999:   i/10, i, "" 
       1000-1M: i/10k, i/1000, k
       1M...    i/10M, i/1M, M 
     for example: 4000000 => 400k 4000k
  */
    var (start, size, unit) = if (problemsize > 9999999) (problemsize/(10*1000*1000), problemsize/(1000*1000), "M") 
    else  if (problemsize > 9999) (problemsize/(10*1000), problemsize/1000, "k") 
    else (problemsize/10, problemsize, "")
    	
    val cmd = "# set terminal png transparent nocrop enhanced font arial 8 size 420,320\n" +
              "set output '" + name + ".png'\n" + 
              "set terminal png\n" + 
              "set ylabel 'Time in s'\n" +
              "set xlabel 'Problem size from " + start + unit + " to " + size + unit + "\n" +
              "set style data linespoints\n" +
              "set xtics border in scale 1,0.5 nomirror offset character 0, 0, 0\n" + 
              "set title 'performance comparision v0.3'\n" +
              "plot '" + name + ".data' using 2:xtic(1) t 2\n" 
    val ext = for (i <- 2 to list2bench.size) yield "'' u " + (i+1) + " t " + (i+1)
    cmd + ext.mkString (", ", ", ", " ") + "\n"
  }
}

UniqueSortedFilteredBench.scala

import annotation.tailrec 

object UniqueSortedFilteredBench extends Benchcoat [Array[Int], List[Int]] {
  
  val name = "usfBench"
  def iGenerator (n: Int) = (for (x <- 1 to n) yield (r.nextInt (n))).toArray 
  def takePart (li: Array[Int], n: Int) = li.take (n) 

// ----------
  
  def danielCsUSF (someArray: Array[Int]): List[Int] = {
    val a = scala.collection.immutable.SortedSet (someArray filter (0 !=): _*)
    a.toList
  }
    
  def luigiPlingeUSF (someArray: Array[Int]): List[Int] =
    collection.SortedSet (someArray.filter (_ > 0) :_*).toList
  
  def matthewFarwellUSF (someArray: Array[Int]): List[Int] = {
    val a = someArray.toSet.filter (_ > 0).toArray
    java.util.Arrays.sort (a) // quicksort, mutable data structures bad :-)
    a.toList
  }
  
  def rexKerrUSF (someArray: Array[Int]): List[Int] = {
    java.util.Arrays.sort (someArray)
    var overzero = 0
    var ndiff = 0
    var last = 0
    var i = 0
    while (i < someArray.length) {
      if (someArray (i) <= 0) overzero += 1
      else if (someArray (i) > last) {
        last = someArray (i)
        ndiff += 1
      }
      i += 1
    }
    var result = List [Int] ()
    var j = 0
    i = overzero
    last = 0
    while (i < someArray.length) {
      if (someArray (i) > last) {
        result = someArray (i) :: result
        last = someArray (i)
        j += 1
      }
      i += 1
    }
    result
  }

  def jedWesleySmithUSF (someArray: Array[Int]): List[Int] = {
		util.Sorting.quickSort (someArray)
  	someArray.foldRight (List.empty [Int]) { 
		case (a, b) => 
		  if (!b.isEmpty && b(0) == a) 
		    b 
		  else 
		    a :: b 
	  }
  }
  
  def userUnknownUSF (someArray: Array[Int]): List[Int] =
    someArray.toList.filter (_ > 0).sortWith (_ > _).distinct

// -----------------------

  val list2bench: List [(String, Array[Int] => List[Int])] = List (
      "danielCsUSF"        -> danielCsUSF _
      , "luigiPlingeUSF"   -> luigiPlingeUSF _
      , "matthewFarwellUSF"-> matthewFarwellUSF _
      , "rexKerrUSF"       -> rexKerrUSF _
      , "jedWesleySmithUSF"-> jedWesleySmithUSF _
      , "userUnknownUSF"   -> userUnknownUSF _
  )
}