Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
A benchmark to compare different algorithms with increasing sample size
/**
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 _
)
}
Owner

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

Owner

bench.plotset 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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment