Last active
August 29, 2015 14:02
-
-
Save bkovitz/95b4bf043cc758346878 to your computer and use it in GitHub Desktop.
Scala Option[Collection] benchmark
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
/* | |
* Benchmarks of answers posted to http://stackoverflow.com/questions/23914713 | |
* "How do you stop building an Option[Collection] upon reaching the first None?" | |
* | |
* Results: | |
* | |
* version ms per iteration | |
* ------- ---------------- | |
* allPartsIterator: 0.001022 | |
* allPartsMatchReturn: 0.001544 | |
* allPartsReturn: 0.002187 | |
* allPartsWithView: 0.002808 | |
* allPartsBruteForce: 0.003159 | |
* allPartsWithMutableFlag: 0.003345 | |
* allPartsRecursive: 0.003753 | |
* allPartsFoldLeft: 0.003873 | |
* allPartsWithStream: 0.008794 | |
* | |
* Environment: | |
* Scala 2.11.1 | |
* JVM 1.7.0_55 | |
* Intel(R) Core(TM)2 Duo CPU E8400 @ 3.00GHz | |
* Red Hat Enterprise Linux Workstation release 6.5 (Santiago) | |
*/ | |
import scala.annotation.tailrec | |
import java.lang.management.ManagementFactory | |
object benchmark { | |
val mxbean = ManagementFactory.getThreadMXBean() | |
def timeMillis[A](func: => A): Double = { | |
val startTime = mxbean.getCurrentThreadCpuTime() | |
func | |
val endTime = mxbean.getCurrentThreadCpuTime() | |
(endTime - startTime) / 1e6 | |
} | |
case class Part(name: String) | |
val partNames = List( | |
"steering wheel", "rudder", "pointy thing at front", | |
"captain's chair", "the box", "large, helium-filled part", | |
"propeller", "cigarette lighter", "ashtray", "Zeppelin logo" | |
) | |
def findPartByName(name: String): Option[Part] = | |
// linear search & object creation to make this function a little bit | |
// expensive | |
partNames.find(_ == name) flatMap { name => Some(Part(name)) } | |
def allPartsTime(allFinder: Seq[String] => Option[Seq[Part]]): Double = { | |
val numReps = 2000000 | |
timeMillis { | |
for (i <- 1 to numReps) { | |
allFinder(Seq( | |
"steering wheel", "rudder", "pointy thing at front", | |
"captain's chair", "the box", "large, helium-filled part", | |
"propeller", "cigarette lighter", "ashtray", "Zeppelin logo" | |
)) | |
allFinder(Seq.empty) | |
allFinder(Seq( | |
"non-existent Gothic cathedral", | |
"steering wheel", "rudder", "pointy thing at front", | |
"captain's chair", "the box", "large, helium-filled part", | |
"propeller", "cigarette lighter", "ashtray", "Zeppelin logo" | |
)) | |
} | |
} / numReps | |
} | |
def allPartsFoldLeft(names: Seq[String]): Option[Seq[Part]] = | |
names.foldLeft(Some(Seq.empty): Option[Seq[Part]]) { | |
(result, name) => result match { | |
case Some(parts) => | |
findPartByName(name) flatMap { part => Some(parts :+ part) } | |
case None => None | |
} | |
} | |
def allPartsMatchReturn(names: Seq[String]): Option[Seq[Part]] = Some( | |
for (name <- names) yield findPartByName(name) match { | |
case Some(part) => part | |
case None => return None | |
} | |
) | |
def allPartsIterator(names: Seq[String]): Option[Seq[Part]] = { | |
val iterator = names.iterator | |
var accum = List.empty[Part] | |
while (iterator.hasNext) { | |
findPartByName(iterator.next) match { | |
case Some(part) => accum +:= part | |
case None => return None | |
} | |
} | |
Some(accum.reverse) | |
} | |
def allPartsRecursive(names: Seq[String]): Option[Seq[Part]] = { | |
@tailrec | |
def allPartsRec(names: Seq[String], acc: Seq[Part]): | |
Option[Seq[Part]] = names match { | |
case Seq(x, xs@_*) => findPartByName(x) match { | |
case Some(part) => allPartsRec(xs, acc :+ part) | |
case None => None | |
} | |
case _ => Some(acc) | |
} | |
allPartsRec(names, Seq.empty) | |
} | |
def allPartsWithView(names: Seq[String]): Option[Seq[Part]] = { | |
val successes = names.view.map(findPartByName) | |
.takeWhile(!_.isEmpty) | |
.map(_.get) | |
.force | |
if (!names.isDefinedAt(successes.size)) Some(successes) | |
else None | |
} | |
def allPartsWithStream(names: Seq[String]): Option[Seq[Part]] = { | |
val (good, bad) = names.toStream.map(findPartByName) | |
.span(!_.isEmpty) | |
if (bad.isEmpty) Some(good.map(_.get).toList) | |
else None | |
} | |
def allPartsReturn(names: Seq[String]): Option[Seq[Part]] = Some( | |
names.map(findPartByName(_) getOrElse { return None }) | |
) | |
def allPartsWithMutableFlag(names: Seq[String]): Option[Seq[Part]] = { | |
var failed = false | |
val parts = names map { name => findPartByName(name) match { | |
case Some(part) => Some(part) | |
case None => failed = true; None | |
}} takeWhile(_.nonEmpty) | |
if (failed) None else Some(parts.flatten) | |
} | |
def allPartsBruteForce(names: Seq[String]): Option[Seq[Part]] = { | |
val parts = names.map(findPartByName(_)) | |
if (parts contains None) None else Some(parts.flatten) | |
} | |
def singleTest(allFinder: Seq[String] => Option[Seq[Part]]) { | |
println(allFinder(Seq( | |
"steering wheel", "rudder", "pointy thing at front", | |
"captain's chair", "the box", "large, helium-filled part", | |
"propeller", "cigarette lighter", "ashtray", "Zeppelin logo" | |
))) | |
println(allFinder(Seq.empty)) | |
println(allFinder(Seq( | |
"non-existent Gothic cathedral", | |
"steering wheel", "rudder", "pointy thing at front", | |
"captain's chair", "the box", "large, helium-filled part", | |
"propeller", "cigarette lighter", "ashtray", "Zeppelin logo" | |
))) | |
} | |
def main(args: Array[String]) { | |
val funcs = Seq( | |
("allPartsFoldLeft", allPartsFoldLeft _), | |
("allPartsMatchReturn", allPartsMatchReturn _), | |
("allPartsIterator", allPartsIterator _), | |
("allPartsRecursive", allPartsRecursive _), | |
("allPartsWithView", allPartsWithView _), | |
("allPartsWithStream", allPartsWithStream _), | |
("allPartsWithMutableFlag", allPartsWithMutableFlag _), | |
("allPartsReturn", allPartsReturn _), | |
("allPartsBruteForce", allPartsBruteForce _) | |
) | |
val results = funcs.map(pair => | |
(pair._1, allPartsTime(pair._2))).sortBy(_._2) | |
for (result <- results) | |
println(f"${result._1 + ':'}%-24s ${result._2}%8.6f") | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment