Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Benchmark code for algorithms in this Stack Overflow question regarding Java vs Scala performance: http://stackoverflow.com/q/7084212/53013
// 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
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.