Skip to content

Instantly share code, notes, and snippets.

@Stefan-Wagner
Created August 17, 2011 22:18
Show Gist options
  • Save Stefan-Wagner/1152783 to your computer and use it in GitHub Desktop.
Save Stefan-Wagner/1152783 to your computer and use it in GitHub Desktop.
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 _
)
}
@Stefan-Wagner
Copy link
Author

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

@Stefan-Wagner
Copy link
Author

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

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