53 case 1 => r |
53 case 1 => r |
54 case n => SEQ(r, NTIMES(r, n - 1)) |
54 case n => SEQ(r, NTIMES(r, n - 1)) |
55 } |
55 } |
56 |
56 |
57 // the evil regular expression a?{n} a{n} |
57 // the evil regular expression a?{n} a{n} |
58 def EVIL(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) |
58 def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) |
|
59 val EVIL2 = SEQ(STAR(CHAR('a')), CHAR('b')) |
59 |
60 |
60 //for measuring time |
61 //for measuring time |
61 def time_needed[T](i: Int, code: => T) = { |
62 def time_needed[T](i: Int, code: => T) = { |
62 val start = System.nanoTime() |
63 val start = System.nanoTime() |
63 for (j <- 1 to i) code |
64 for (j <- 1 to i) code |
64 val end = System.nanoTime() |
65 val end = System.nanoTime() |
65 (end - start)/(i * 1.0e9) |
66 (end - start)/(i * 1.0e9) |
66 } |
67 } |
67 |
68 |
68 |
69 |
69 for (i <- 1 to 29) { |
70 for (i <- 1 to 20) { |
70 println(i + ": " + "%.5f".format(time_needed(1, matches(EVIL(i), "a" * i)))) |
71 println(i + ": " + "%.5f".format(time_needed(2, matches(EVIL1(i), "a" * i)))) |
71 } |
72 } |
72 |
73 |
|
74 for (i <- 1 to 6502 by 500) { |
|
75 println(i + " " + "%.5f".format(time_needed(2, matches(EVIL2, "a" * i)))) |
|
76 } |
73 |
77 |