public
Last active

A benchmark to compare different algorithms with increasing sample size

  • Download Gist
Benchcoat.scala
Scala
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229
/**
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).
 
(c) 2011 GPLv3
This, newest version contains some code, to write a short gnuplot-code
and the gnuplot data to two files, to make a diagram out of the test data.
*/
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 random Ints
def iGenerator (n: Int) : I
// typical case: list.take (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 (prettyPrint)
// 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 (prettyPrint, "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 prettyPrint : 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 prettyPrint1 = {
/* 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"
plot 'bench.data' using 2:xtic(1) t 2"""
val ext = for (i <- 3 to buf.size / 11) yield "'' u " + i + " t " + i
cmd + ext.mkString (", ", ", ", " ")
}
}
 
/**
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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.