Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
BenchcoatImplementation
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

Likes 81 and 82 should be:

implicit def enhanceSeq[A, Repr <: Seq[A]](seq: SeqLike[A, Repr]) = new EnhancedSeq(seq)
i.dropRightWhile(_ == 0)
@Stefan-Wagner

@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
Something went wrong with that request. Please try again.