equal
deleted
inserted
replaced
|
1 // version with explicit n-times regular expression |
|
2 |
1 abstract class Rexp |
3 abstract class Rexp |
2 case object NULL extends Rexp |
4 case object NULL extends Rexp |
3 case object EMPTY extends Rexp |
5 case object EMPTY extends Rexp |
4 case class CHAR(c: Char) extends Rexp |
6 case class CHAR(c: Char) extends Rexp |
5 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
7 case class ALT(r1: Rexp, r2: Rexp) extends Rexp |
39 |
41 |
40 |
42 |
41 //optional: one or zero times |
43 //optional: one or zero times |
42 def OPT(r: Rexp) = ALT(r, EMPTY) |
44 def OPT(r: Rexp) = ALT(r, EMPTY) |
43 |
45 |
|
46 //evil regular expressions |
44 def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) |
47 def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n)) |
45 val EVIL2 = SEQ(STAR(CHAR('a')), CHAR('b')) |
48 val EVIL2 = SEQ(STAR(CHAR('a')), CHAR('b')) |
46 |
49 |
47 def time_needed[T](i: Int, code: => T) = { |
50 def time_needed[T](i: Int, code: => T) = { |
48 val start = System.nanoTime() |
51 val start = System.nanoTime() |
53 |
56 |
54 for (i <- 1 to 100) { |
57 for (i <- 1 to 100) { |
55 println(i + ": " + "%.5f".format(time_needed(1, matches(EVIL1(i), "a" * i)))) |
58 println(i + ": " + "%.5f".format(time_needed(1, matches(EVIL1(i), "a" * i)))) |
56 } |
59 } |
57 |
60 |
58 //a bit bolder test |
61 //a bit bolder tests |
59 for (i <- 1 to 1001 by 50) { |
62 for (i <- 1 to 1001 by 50) { |
60 println(i + " " + "%.5f".format(time_needed(2, matches(EVIL1(i), "a" * i)))) |
63 println(i + " " + "%.5f".format(time_needed(2, matches(EVIL1(i), "a" * i)))) |
61 } |
64 } |
62 |
65 |
63 |
66 |