diff options
author | Aleksandar Prokopec <aleksandar.prokopec@gmail.com> | 2012-01-30 02:17:08 -0800 |
---|---|---|
committer | Aleksandar Prokopec <aleksandar.prokopec@gmail.com> | 2012-01-30 02:17:08 -0800 |
commit | bdb3fc80514c6c105e3a5edcb6a040ba2f6be3e3 (patch) | |
tree | 01f1d71b1858c435b23f49cd4aabba6e1df06949 /test | |
parent | 5e9dd4a05c25f463f29d0fbc2f1bec194bf7700b (diff) | |
parent | 06945b6dcfc7bbb0efb5f8429ffeab7fbde9be5b (diff) | |
download | scala-bdb3fc80514c6c105e3a5edcb6a040ba2f6be3e3.tar.gz scala-bdb3fc80514c6c105e3a5edcb6a040ba2f6be3e3.tar.bz2 scala-bdb3fc80514c6c105e3a5edcb6a040ba2f6be3e3.zip |
Merge pull request #1 from lpereir4/avl
AvlTree performance improvements
Diffstat (limited to 'test')
-rw-r--r-- | test/benchmarking/TreeSetInsert.scala | 65 | ||||
-rw-r--r-- | test/benchmarking/TreeSetInsertRandom.scala | 65 | ||||
-rw-r--r-- | test/benchmarking/TreeSetIterator.scala | 66 | ||||
-rw-r--r-- | test/benchmarking/TreeSetRemove.scala | 66 | ||||
-rw-r--r-- | test/benchmarking/TreeSetRemoveRandom.scala | 66 | ||||
-rw-r--r-- | test/files/scalacheck/avl.scala | 114 |
6 files changed, 442 insertions, 0 deletions
diff --git a/test/benchmarking/TreeSetInsert.scala b/test/benchmarking/TreeSetInsert.scala new file mode 100644 index 0000000000..61b064ae33 --- /dev/null +++ b/test/benchmarking/TreeSetInsert.scala @@ -0,0 +1,65 @@ + +object TreeSetInsert { + + def main(args: Array[String]): Unit = { + val n = 500000 + new JavaUtilTS(n).main(args) + new MutableTS(n).main(args) + new ImmutableTS(n).main(args) + } +} + +class Dummy(val a: Int) extends math.Ordered[Dummy] { + def compare(other: Dummy) = this.a - other.a + + override def toString = a.toString + } + + +class JavaUtilTS(val length: Int) extends testing.Benchmark { + var data: Array[Dummy] = (0 until length) map { a => new Dummy(a) } toArray + var t: java.util.TreeSet[Dummy] = null + + def run = { + t = new java.util.TreeSet[Dummy]() + + var i = 0 + while (i < length) { + val elem = data(i) + t add elem + i += 1 + } + } +} + +class MutableTS(val length: Int) extends testing.Benchmark { + var data: Array[Dummy] = (0 until length) map { a => new Dummy(a) } toArray + var t: collection.mutable.TreeSet[Dummy] = null + + def run = { + t = collection.mutable.TreeSet[Dummy]() + + var i = 0 + while (i < length) { + val elem = data(i) + t += elem + i += 1 + } + } +} + +class ImmutableTS(val length: Int) extends testing.Benchmark { + var data: Array[Dummy] = (0 until length) map { a => new Dummy(a) } toArray + var t: collection.immutable.TreeSet[Dummy] = null + + def run = { + t = collection.immutable.TreeSet[Dummy]() + + var i = 0 + while (i < length) { + val elem = data(i) + t += elem + i += 1 + } + } +} diff --git a/test/benchmarking/TreeSetInsertRandom.scala b/test/benchmarking/TreeSetInsertRandom.scala new file mode 100644 index 0000000000..7f182548b7 --- /dev/null +++ b/test/benchmarking/TreeSetInsertRandom.scala @@ -0,0 +1,65 @@ + +object TreeSetInsertRandom { + + def main(args: Array[String]): Unit = { + val n = 500000 + new JavaUtilTS(n).main(args) + new MutableTS(n).main(args) + new ImmutableTS(n).main(args) + } +} + +class Dummy(val a: Int) extends math.Ordered[Dummy] { + def compare(other: Dummy) = this.a - other.a + + override def toString = a.toString + } + + +class JavaUtilTS(val length: Int) extends testing.Benchmark { + var data: Array[Dummy] = util.Random.shuffle((0 until length) map { a => new Dummy(a) }) toArray + var t: java.util.TreeSet[Dummy] = null + + def run = { + t = new java.util.TreeSet[Dummy]() + + var i = 0 + while (i < length) { + val elem = data(i) + t add elem + i += 1 + } + } +} + +class MutableTS(val length: Int) extends testing.Benchmark { + var data: Array[Dummy] = util.Random.shuffle((0 until length) map { a => new Dummy(a) }) toArray + var t: collection.mutable.TreeSet[Dummy] = null + + def run = { + t = collection.mutable.TreeSet[Dummy]() + + var i = 0 + while (i < length) { + val elem = data(i) + t += elem + i += 1 + } + } +} + +class ImmutableTS(val length: Int) extends testing.Benchmark { + var data: Array[Dummy] = util.Random.shuffle((0 until length) map { a => new Dummy(a) }) toArray + var t: collection.immutable.TreeSet[Dummy] = null + + def run = { + t = collection.immutable.TreeSet[Dummy]() + + var i = 0 + while (i < length) { + val elem = data(i) + t += elem + i += 1 + } + } +} diff --git a/test/benchmarking/TreeSetIterator.scala b/test/benchmarking/TreeSetIterator.scala new file mode 100644 index 0000000000..c3b19aa29f --- /dev/null +++ b/test/benchmarking/TreeSetIterator.scala @@ -0,0 +1,66 @@ + +object TreeSetIterator { + + def main(args: Array[String]): Unit = { + val n = 500000 + new JavaUtilTS(n).main(args) + new MutableTS(n).main(args) + new ImmutableTS(n).main(args) + } +} + +class Dummy(val a: Int) extends math.Ordered[Dummy] { + def compare(other: Dummy) = this.a - other.a + + override def toString = a.toString + } + + +class JavaUtilTS(val length: Int) extends testing.Benchmark { + var data: Array[Dummy] = (0 until length) map { a => new Dummy(a) } toArray + var t: java.util.TreeSet[Dummy] = null + + def run = { + t = new java.util.TreeSet[Dummy]() + data foreach { a => t add a } + + var i: Dummy = null + var it = t.iterator + while (it.hasNext) { + i = it.next + } + i + } +} + +class MutableTS(val length: Int) extends testing.Benchmark { + var data: Array[Dummy] = (0 until length) map { a => new Dummy(a) } toArray + var t: collection.mutable.TreeSet[Dummy] = null + + def run = { + t = collection.mutable.TreeSet[Dummy](data: _*) + + var i: Dummy = null + var it = t.iterator + while (it.hasNext) { + i = it.next + } + i + } +} + +class ImmutableTS(val length: Int) extends testing.Benchmark { + var data: Array[Dummy] = (0 until length) map { a => new Dummy(a) } toArray + var t: collection.immutable.TreeSet[Dummy] = null + + def run = { + t = collection.immutable.TreeSet[Dummy](data: _*) + + var i: Dummy = null + var it = t.iterator + while (it.hasNext) { + i = it.next + } + i + } +} diff --git a/test/benchmarking/TreeSetRemove.scala b/test/benchmarking/TreeSetRemove.scala new file mode 100644 index 0000000000..68c07ce70a --- /dev/null +++ b/test/benchmarking/TreeSetRemove.scala @@ -0,0 +1,66 @@ + +object TreeSetRemove { + + def main(args: Array[String]): Unit = { + val n = 500000 + new JavaUtilTS(n).main(args) + new MutableTS(n).main(args) + new ImmutableTS(n).main(args) + } +} + +class Dummy(val a: Int) extends math.Ordered[Dummy] { + def compare(other: Dummy) = this.a - other.a + + override def toString = a.toString + } + + +class JavaUtilTS(val length: Int) extends testing.Benchmark { + var data: Array[Dummy] = (0 until length) map { a => new Dummy(a) } toArray + var t: java.util.TreeSet[Dummy] = null + + def run = { + t = new java.util.TreeSet[Dummy]() + data foreach { a => t add a } + + var i = 0 + while (i < length) { + val elem = data(i) + t remove elem + i += 1 + } + } +} + +class MutableTS(val length: Int) extends testing.Benchmark { + var data: Array[Dummy] = (0 until length) map { a => new Dummy(a) } toArray + var t: collection.mutable.TreeSet[Dummy] = null + + def run = { + t = collection.mutable.TreeSet[Dummy](data: _*) + + var i = 0 + while (i < length) { + val elem = data(i) + t -= elem + i += 1 + } + } +} + +class ImmutableTS(val length: Int) extends testing.Benchmark { + var data: Array[Dummy] = (0 until length) map { a => new Dummy(a) } toArray + var t: collection.immutable.TreeSet[Dummy] = null + + def run = { + t = collection.immutable.TreeSet[Dummy](data: _*) + + var i = 0 + while (i < length) { + val elem = data(i) + t -= elem + i += 1 + } + } +} diff --git a/test/benchmarking/TreeSetRemoveRandom.scala b/test/benchmarking/TreeSetRemoveRandom.scala new file mode 100644 index 0000000000..4d311679e3 --- /dev/null +++ b/test/benchmarking/TreeSetRemoveRandom.scala @@ -0,0 +1,66 @@ + +object TreeSetRemoveRandom { + + def main(args: Array[String]): Unit = { + val n = 500000 + new JavaUtilTS(n).main(args) + new MutableTS(n).main(args) + new ImmutableTS(n).main(args) + } +} + +class Dummy(val a: Int) extends math.Ordered[Dummy] { + def compare(other: Dummy) = this.a - other.a + + override def toString = a.toString + } + + +class JavaUtilTS(val length: Int) extends testing.Benchmark { + var data: Array[Dummy] = util.Random.shuffle((0 until length) map { a => new Dummy(a) }) toArray + var t: java.util.TreeSet[Dummy] = null + + def run = { + t = new java.util.TreeSet[Dummy]() + data foreach { a => t add a } + + var i = 0 + while (i < length) { + val elem = data(i) + t remove elem + i += 1 + } + } +} + +class MutableTS(val length: Int) extends testing.Benchmark { + var data: Array[Dummy] = util.Random.shuffle((0 until length) map { a => new Dummy(a) }) toArray + var t: collection.mutable.TreeSet[Dummy] = null + + def run = { + t = collection.mutable.TreeSet[Dummy](data: _*) + + var i = 0 + while (i < length) { + val elem = data(i) + t -= elem + i += 1 + } + } +} + +class ImmutableTS(val length: Int) extends testing.Benchmark { + var data: Array[Dummy] = util.Random.shuffle((0 until length) map { a => new Dummy(a) }) toArray + var t: collection.immutable.TreeSet[Dummy] = null + + def run = { + t = collection.immutable.TreeSet[Dummy](data: _*) + + var i = 0 + while (i < length) { + val elem = data(i) + t -= elem + i += 1 + } + } +} diff --git a/test/files/scalacheck/avl.scala b/test/files/scalacheck/avl.scala new file mode 100644 index 0000000000..51fb1fe8c3 --- /dev/null +++ b/test/files/scalacheck/avl.scala @@ -0,0 +1,114 @@ +import org.scalacheck.Gen +import org.scalacheck.Prop.forAll +import org.scalacheck.Properties + +import util.logging.ConsoleLogger + +package scala.collection.mutable { + + /** + * Property of an AVL Tree : Any node of the tree has a balance value beetween in [-1; 1] + */ + abstract class AVLTreeTest(name: String) extends Properties(name) with ConsoleLogger { + + def `2^`(n: Int) = (1 to n).fold(1)((a, b) => b*2) + + def capacityMax(depth: Int): Int = `2^`(depth+1) - 1 + + def minDepthForCapacity(x: Int): Int = { + var depth = 0 + while(capacityMax(depth) < x) + depth += 1 + depth + } + + def numberOfElementsInLeftSubTree(n: Int): collection.immutable.IndexedSeq[Int] = { + val mid = n/2 + n%2 + ((1 until mid) + .filter { i => math.abs(minDepthForCapacity(i) - minDepthForCapacity(n-i)) < 2 } + .flatMap { i => Seq(i, n-(i+1)) }).toIndexedSeq.distinct + } + + def makeAllBalancedTree[A](elements: List[A]): List[AVLTree[A]] = elements match { + case Nil => Leaf::Nil + case first::Nil => Node(first, Leaf, Leaf)::Nil + case first::second::Nil => Node(second, Node(first, Leaf, Leaf), Leaf)::Node(first, Leaf, Node(second, Leaf, Leaf))::Nil + case first::second::third::Nil => Node(second, Node(first, Leaf, Leaf), Node(third, Leaf, Leaf))::Nil + case _ => { + val combinations = for { + left <- numberOfElementsInLeftSubTree(elements.size) + root = elements(left) + right = elements.size - (left + 1) + } yield (root, left, right) + (combinations.flatMap(triple => for { + l <- makeAllBalancedTree(elements.take(triple._2)) + r <- makeAllBalancedTree(elements.takeRight(triple._3)) + } yield Node(triple._1, l, r))).toList + } + } + + def genInput: Gen[(Int, List[AVLTree[Int]])] = for { + size <- Gen.choose(20, 25) + elements <- Gen.listOfN(size, Gen.choose(0, 1000)) + selected <- Gen.choose(0, 1000) + } yield { + // selected mustn't be in elements already + val list = makeAllBalancedTree(elements.sorted.distinct.map(_*2)) + (selected*2+1, list) + } + + def genInputDelete: Gen[(Int, List[AVLTree[Int]])] = for { + size <- Gen.choose(20, 25) + elements <- Gen.listOfN(size, Gen.choose(0, 1000)) + e = elements.sorted.distinct + selected <- Gen.choose(0, e.size-1) + } yield { + // selected must be in elements already + val list = makeAllBalancedTree(e) + (e(selected), list) + } + } + + trait AVLInvariants { + self: AVLTreeTest => + + def isBalanced[A](t: AVLTree[A]): Boolean = t match { + case node: Node[A] => math.abs(node.balance) < 2 && (List(node.left, node.right) forall isBalanced) + case Leaf => true + } + + def setup(invariant: AVLTree[Int] => Boolean) = forAll(genInput) { + case (selected: Int, trees: List[AVLTree[Int]]) => + trees.map(tree => invariant(tree)).fold(true)((a, b) => a && b) + } + + property("Every tree is initially balanced.") = setup(isBalanced) + } + + object TestInsert extends AVLTreeTest("Insert") with AVLInvariants { + import math.Ordering.Int + property("`insert` creates a new tree containing the given element. The tree remains balanced.") = forAll(genInput) { + case (selected: Int, trees: List[AVLTree[Int]]) => + trees.map(tree => { + val modifiedTree = tree.insert(selected, Int) + modifiedTree.contains(selected, Int) && isBalanced(modifiedTree) + }).fold(true)((a, b) => a && b) + } + } + + object TestRemove extends AVLTreeTest("Remove") with AVLInvariants { + import math.Ordering.Int + property("`remove` creates a new tree without the given element. The tree remains balanced.") = forAll(genInputDelete) { + case (selected: Int, trees: List[AVLTree[Int]]) => + trees.map(tree => { + val modifiedTree = tree.remove(selected, Int) + tree.contains(selected, Int) && !modifiedTree.contains(selected, Int) && isBalanced(modifiedTree) + }).fold(true)((a, b) => a && b) + } + } +} + +object Test extends Properties("AVL") { + include(scala.collection.mutable.TestInsert) + include(scala.collection.mutable.TestRemove) +}
\ No newline at end of file |