public

BenchcoatImplementation

  • Download Gist
DropRightConditionalBench.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
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 _
)
}

Likes 81 and 82 should be:

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

@dhgarrette: I updted the code. Sorry for reacting that late, but I'm pretty new to github and a rare visitor.

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.