83 |
83 |
84 // main matcher function |
84 // main matcher function |
85 def matcher(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) |
85 def matcher(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r)) |
86 |
86 |
87 |
87 |
88 |
|
89 //one or zero |
88 //one or zero |
90 def OPT(r: Rexp) = ALT(r, EMPTY) |
89 def OPT(r: Rexp) = ALT(r, EMPTY) |
91 |
90 |
92 def RTEST(n: Int) = SEQ(NTIMES(OPT("a"), n), NTIMES("a", n)) |
91 def EVIL(n: Int) = SEQ(NTIMES(OPT("a"), n), NTIMES("a", n)) |
93 |
92 |
94 def time_needed[T](i: Int, code: => T) = { |
93 def time_needed[T](i: Int, code: => T) = { |
95 val start = System.nanoTime() |
94 val start = System.nanoTime() |
96 for (j <- 1 to i) code |
95 for (j <- 1 to i) code |
97 val end = System.nanoTime() |
96 val end = System.nanoTime() |
98 (end - start)/(i * 1.0e9) |
97 (end - start)/(i * 1.0e9) |
99 } |
98 } |
100 |
99 |
101 |
100 |
102 for (i <- 1 to 11001 by 500) { |
101 for (i <- 1 to 11001 by 500) { |
103 println(i + " " + + " " + time_needed(1, matcher(RTEST(i), "a" * i))) |
102 println(i + " " + "%.5f".format(time_needed(1, matcher(EVIL(i), "a" * i)))) |
104 } |
103 } |
105 |
104 |
106 |
105 |