Created
May 23, 2012 04:10
-
-
Save Stefan-Wagner/2773229 to your computer and use it in GitHub Desktop.
BenchcoatImplementation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import annotation.tailrec | |
// http://stackoverflow.com/questions/10710954/how-do-i-remove-trailing-elements-in-a-scala-collection/10711396#10710954 | |
object DropRightConditionalBench extends Benchcoat [List[Int], List[Int]] { | |
type I=List[Int] | |
type O=List[Int] | |
/** | |
we choose a name for the diagram title and report/data-files, and implement 2 methods: | |
*/ | |
val name = "dropRightConditional" | |
/** | |
first: for the size of the comparision, typically 1M, 10M, 100M elements, how do we create | |
the input of type I? Well - we just return a List of 4-digit random number here. | |
In rare cases, you don't use a collection, but maybe a prime of n digits. | |
*/ | |
// def iGenerator (n: Int) : I = (for (x <- 1 to n) yield random.nextInt (2) % 2).toList | |
def iGenerator (n: Int) : I = (for (x <- 1 to n) yield random.nextInt (1000) / 998).toList | |
/* | |
The benchmark is approaching the final value stepwise. | |
For a final value of 1M, it starts with 100k, 200k, ... 900k, 1M, to see, whether it is a | |
linear process, a logarithmic one or quadratic, and how much single points are outliners, | |
maybe due to GC running. | |
takePart is the technique to take only a sample from the result of iGenerator | |
*/ | |
def takePart (li: I, n: Int) : I = li.take (n) | |
// ---------- | |
/* | |
Step 2: include the methods to compare. We have to give them distinct names. In a competition, | |
the name of the competitor would be usefull (AnnDigitbench, BobDigitbench, ... ZoeDigitbench); | |
if you compare different approaches, a significant characteistic of the code snippet is useful | |
like unfoldDigits, matchDigits, whileDigits and toStringDigits. A more mechanical way would be | |
to name them (digits1, digits2, ...digitsZ). | |
Here I use both, one as Interface to the benchmark, which just performs a mapping | |
to the elementary method. | |
*/ | |
// andyczerwonka | |
def andyczerwonka (i: I): O = { | |
i.take (i.lastIndexWhere(_ != 0)) | |
} | |
// danielCsobral1 | |
def danielCsobral1 (i: I): O = { | |
val seq = i.toSeq | |
seq.reverse.dropWhile (_ == 0).reverse.toList | |
} | |
// danielCsobral2 | |
def danielCsobral2 (i: I): O = { | |
val seq = i.toSeq | |
val s = if (seq(seq.length - 1) == 0) seq take (seq lastIndexOf 0) else seq | |
s.toList | |
} | |
// dhg | |
def dhg (i: I): O = { | |
import scala.collection.SeqLike | |
import scala.collection.generic.CanBuildFrom | |
class EnhancedSeq[A, Repr <: Seq[A]](seq: SeqLike[A, Repr]) { | |
def dropRightWhile[That](p: A => Boolean)(implicit bf: CanBuildFrom[Repr, A, That]): That = { | |
val b = bf (seq.asInstanceOf[Repr]) | |
val buffer = collection.mutable.Buffer[A]() | |
for (x <- seq) { | |
buffer += x | |
if (!p(x)) { | |
b ++= buffer | |
buffer.clear() | |
} | |
} | |
b.result | |
} | |
} | |
// updated, see comment | |
implicit def enhanceSeq [A, Repr <: Seq[A]] (seq: SeqLike [A, Repr]) = | |
new EnhancedSeq (seq) | |
i.dropRightWhile (_ == 0) | |
/* | |
implicit def enhanceSeq [A, Repr <: Seq[A]] (seq: SeqLike [A, Repr]) = | |
new EnhancedSeq (seq) | |
i.toSeq.dropRightWhile (_ == 0) | |
*/ | |
} | |
// Rex Kerr 1 | |
def rexKerr1 (i: I): O = { | |
i.reverse.dropWhile(_ == 0).reverse | |
} | |
// Rex Kerr 2 | |
def rexKerr2 (list: I): O = { | |
(list :\ list.take(0)){ (x,ys) => if (x==0 && ys.isEmpty) ys else x :: ys } | |
} | |
// Rex Kerr 3 | |
def rexKerr3 (i: I): O = { | |
@tailrec | |
def customDropZeros (xs: I, buffer: Array[Int] = new Array[Int](16), n: Int = 0): O = { | |
if (xs.isEmpty) { | |
var ys = xs | |
var m = n | |
while (m>0 && buffer(m-1)==0) m -= 1 | |
var i = m-1 | |
while (i>=0) { | |
ys = buffer(i) :: ys | |
i -= 1 | |
} | |
ys | |
} | |
else { | |
val b2 = ( | |
if (n<buffer.length) buffer | |
else java.util.Arrays.copyOf(buffer, buffer.length*2) | |
) | |
b2(n) = xs.head | |
customDropZeros(xs.tail, b2, n+1) | |
} | |
} | |
customDropZeros (i) | |
} | |
// User Unknown Urform | |
def uu1 (i: I): O = { | |
@tailrec | |
def dropRight [T] (l: List[T], p: (T=>Boolean), carry: List[T]=List.empty, buf: List[T]=List.empty) : List[T] = { | |
if (l.isEmpty) carry.reverse else | |
if (p (l.head)) dropRight (l.tail, p, l.head :: buf ::: carry, List.empty) else | |
dropRight (l.tail, p, carry, l.head :: buf) } | |
dropRight (i, (x: Int) => x != 0) | |
} | |
// User Unknown no predicate passing | |
def uu2 (i: I): O = { | |
@tailrec | |
def dropRight [T] (l: List[T], carry: List[T]=List.empty, buf: List[T]=List.empty) : List[T] = { | |
if (l.isEmpty) carry.reverse else | |
if (l.head != 0) dropRight (l.tail, l.head :: buf ::: carry, List.empty) else | |
dropRight (l.tail, carry, l.head :: buf) } | |
dropRight (i) | |
} | |
// User Unknown explicit Int | |
def uu3 (i: I): O = { | |
@tailrec | |
def dropRight [Int] (l: List[Int], carry: List[Int]=List.empty, buf: List[Int]=List.empty) : List[Int] = { | |
if (l.isEmpty) carry.reverse else | |
if (l.head != 0) dropRight (l.tail, l.head :: buf ::: carry, List.empty) else | |
dropRight (l.tail, carry, l.head :: buf) } | |
dropRight (i) | |
} | |
// overflow on high values | |
// def dropRight (l: List[Int], buf: List[Int]=List.empty) : List[Int] = { | |
def uu4 (l: List[Int], buf: List[Int]=List.empty) : List[Int] = { | |
if (l.isEmpty) l else | |
if (l.head != 0) buf ::: l.head :: uu4 (l.tail, List.empty) else | |
uu4 (l.tail, l.head :: buf) } | |
// def uu4 (i: I): O = dropRight (i) | |
/* | |
Step 3: | |
The final step, put them together in a List and let's make party: | |
val list2bench: List [(String, Int => List[Int])] = List ( | |
*/ | |
val list2bench: List [(String, I => O)] = List ( | |
"andyczerwonka" -> andyczerwonka _ | |
, "danielCsobral1" -> danielCsobral1 _ | |
, "danielCsobral2" -> danielCsobral2 _ | |
, "dhg" -> dhg _ | |
, "rexKerr1" -> rexKerr1 _ | |
// , "rexKerr2" -> rexKerr2 _ | |
, "rexKerr3" -> rexKerr3 _ | |
, "uu1"-> uu1 _ | |
// , "uu2"-> uu2 _ | |
// , "uu3"-> uu3 _ | |
) | |
} |
@dhgarrette: I updted the code. Sorry for reacting that late, but I'm pretty new to github and a rare visitor.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Likes 81 and 82 should be: