public
Created

Benchmark code for algorithms in this Stack Overflow question regarding Java vs Scala performance: http://stackoverflow.com/q/7084212/53013

  • Download Gist
BenchCode.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
// Question at http://stackoverflow.com/q/7084212/53013
// Results at https://gist.github.com/1152764
 
import scala.collection.mutable.{ArrayBuffer, ListBuffer}
import scala.util.Random
 
object BenchCode extends scala.testing.Benchmark with Algorithms {
var xs: List[Int] = Nil
var acc = 0
var code: List[Int] => List[Int] = (identity _)
def run() { acc += code(xs).sum }
 
override def main(args: Array[String]) {
if (args.length > 1) {
if (args.length > 2) multiplier = args(2).toInt
 
// Algorithms
val algos = List(
"Adrian, functional/indexOf" -> adrian1 _,
"Adrian, functional/span" -> adrian1b _,
"Adrian, imperative/ArrayBuffer" -> adrian2 _,
"Adrian, imperative/ListBuffer" -> adrian2b _,
"user unknown, recursive" -> (uu2(_: List[Int])),
"user unknown, fold" -> uu3 _,
"paradigmatic, recursive" -> paradigmatic1 _,
"paradigmatic, fold" -> paradigmatic2 _,
"soc" -> soc _
)
val fmt = " %-" + algos.map(_._1.length).max + "s"
 
// Data sources
val sequential = 1 to args(0).toInt toList;
val reverse = sequential.reverse
val distinct = Random.shuffle(sequential)
val random = List.fill(args(0).toInt)(Random.nextInt)
val seqs = List(
"increasing sequence" -> sequential,
"decreasing sequence" -> reverse,
"random no repetitions" -> distinct,
"random with repetitions" -> random
)
 
// Warm up
for ((name, algo) <- algos) {
xs = sequential take 20000
code = algo
println("Warming up "+name)
1 to 20000 foreach { _ => run }
}
 
// For each kind of data
for ((kind, seq) <- seqs) {
println("List type: "+kind)
xs = seq
 
// For each algorithm
for ((name, algo) <- algos) {
code = algo
print(fmt format name)
for (t <- runBenchmark(args(1).toInt))
print("%8d" format t)
println()
}
}
 
// Not enough parameters
} else {
println("Syntax: scala BenchCode ListSize Runs [Multiplier]")
}
}
}
 
trait Algorithms {
def adrian1(xs: List[Int]): List[Int] = {
val maxIndex = xs.indexOf(xs.max);
xs.take(maxIndex) ::: xs.drop(maxIndex+1)
}
 
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 adrian1b(xs: List[Int]): List[Int] = {
val max = xs.max
val (before, _ :: after) = xs span (max !=)
before ::: after
}
 
def adrian2b(xs: 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
}
 
import annotation.tailrec
@tailrec
final def uu2 (xs: List [Int], carry: List [Int] = List.empty) : 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 uu3(xs: 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
 
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
}
 
def soc(xs: List[Int]) = {
val buf = xs.toBuffer
buf -= (buf.max)
buf.toList
}
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.