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
|
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]): Unit = {
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))
}
}
}
|
