diff options
author | Paul Phillips <paulp@improving.org> | 2011-08-09 22:25:37 +0000 |
---|---|---|
committer | Paul Phillips <paulp@improving.org> | 2011-08-09 22:25:37 +0000 |
commit | e3e64e43659f53dd8f9cd5837f78a7e4378dc4c4 (patch) | |
tree | 489d2177d58f73e0c7c63aceb70d7667ab59d779 /test | |
parent | 333f540595b5cc80879758f656cccd99632d3fd5 (diff) | |
download | scala-e3e64e43659f53dd8f9cd5837f78a7e4378dc4c4.tar.gz scala-e3e64e43659f53dd8f9cd5837f78a7e4378dc4c4.tar.bz2 scala-e3e64e43659f53dd8f9cd5837f78a7e4378dc4c4.zip |
Optimizations for Seq's implementations of sequ...
Optimizations for Seq's implementations of sequence search algorithms.
Contributed by Rex Kerr. Closes SI-4828, no review.
Diffstat (limited to 'test')
-rw-r--r-- | test/files/run/kmpSliceSearch.check | 4 | ||||
-rw-r--r-- | test/files/run/kmpSliceSearch.scala | 60 |
2 files changed, 64 insertions, 0 deletions
diff --git a/test/files/run/kmpSliceSearch.check b/test/files/run/kmpSliceSearch.check new file mode 100644 index 0000000000..9ce0eba5a8 --- /dev/null +++ b/test/files/run/kmpSliceSearch.check @@ -0,0 +1,4 @@ +6 6 +5 10 +-1 -1 +4 4 diff --git a/test/files/run/kmpSliceSearch.scala b/test/files/run/kmpSliceSearch.scala new file mode 100644 index 0000000000..e72f78bfed --- /dev/null +++ b/test/files/run/kmpSliceSearch.scala @@ -0,0 +1,60 @@ +object Test { + import scala.collection.SeqLike + def slowSearch[A](xs: Seq[A], ys: Seq[A], start: Int = 0): Int = { + if (xs startsWith ys) start + else if (xs.isEmpty) -1 + else slowSearch(xs.tail, ys, start+1) + } + def bkwSlowSearch[A](xs: Seq[A], ys: Seq[A]) = { + val i = slowSearch(xs.reverse, ys.reverse) + if (i<0) i + else xs.length - ys.length - i + } + def main(args: Array[String]) { + val rng = new scala.util.Random(java.lang.Integer.parseInt("kmp",36)) + + // Make sure we agree with naive implementation + for (h <- Array(2,5,1000)) { + for (i <- 0 to 100) { + for (j <- 0 to 10) { + val xs = (0 to j).map(_ => (rng.nextInt & 0x7FFFFFFF) % h) + val xsa = xs.toArray + val xsv = Vector() ++ xs + val xsl = xs.toList + val xss = Vector[Seq[Int]](xs,xsa,xsv,xsl) + for (k <- 0 to 5) { + val ys = (0 to k).map(_ => (rng.nextInt & 0x7FFFFFFF) % h) + val ysa = ys.toArray + val ysv = Vector() ++ ys + val ysl = ys.toList + val yss = Vector[Seq[Int]](ys,ysa,ysv,ysl) + val fwd_slow = slowSearch(xs,ys) + val bkw_slow = bkwSlowSearch(xs,ys) + val fwd_fast = xss.flatMap(xs => yss.map(ys => SeqLike.indexOf(xs,0,xs.length,ys,0,ys.length,0))) + val bkw_fast = xss.flatMap(xs => yss.map(ys => SeqLike.lastIndexOf(xs,0,xs.length,ys,0,ys.length,xs.length))) + assert(fwd_fast.forall(_ == fwd_slow)) + assert(bkw_fast.forall(_ == bkw_slow)) + } + } + } + } + + // Check performance^Wcorrectness of common small test cases + val haystacks = List[Seq[Int]]( + Array(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15), + Vector(99,2,99,99,2,99,99,99,2,99,99,99,99,2), + List(1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1), + 1 to 15 + ) + val needles = List[Seq[Int]]( + Array(7,8,9,10), + Vector(99,99,99), + List(1,1,1,1,1,2), + 5 to 9 + ) + (haystacks zip needles) foreach { + case (hay, nee) => + println(hay.indexOfSlice(nee,2) + " " + hay.lastIndexOfSlice(nee,13)) + } + } +} |