equal
deleted
inserted
replaced
75 for (j <- 1 to i) code |
75 for (j <- 1 to i) code |
76 val end = System.nanoTime() |
76 val end = System.nanoTime() |
77 (end - start)/(i * 1.0e9) |
77 (end - start)/(i * 1.0e9) |
78 } |
78 } |
79 |
79 |
|
80 |
80 //test: (a?{n}) (a{n}) |
81 //test: (a?{n}) (a{n}) |
81 for (i <- 1 to 20) { |
82 for (i <- 1 to 20) { |
82 println(i + ": " + "%.5f".format(time_needed(2, matches(EVIL1(i), "a" * i)))) |
83 println(i + ": " + "%.5f".format(time_needed(2, matches(EVIL1(i), "a" * i)))) |
83 } |
84 } |
84 |
85 |
113 |
114 |
114 size(EVIL1(1)) // 5 |
115 size(EVIL1(1)) // 5 |
115 size(EVIL1(3)) // 17 |
116 size(EVIL1(3)) // 17 |
116 size(EVIL1(5)) // 29 |
117 size(EVIL1(5)) // 29 |
117 size(EVIL1(7)) // 41 |
118 size(EVIL1(7)) // 41 |
|
119 |
|
120 |
|
121 // given a regular expression and building successive |
|
122 // derivatives might result into bigger and bigger |
|
123 // regular expressions...here is an example for this: |
|
124 |
|
125 val BIG_aux = STAR(ALT(CHAR('a'), CHAR('b'))) |
|
126 val BIG = SEQ(BIG_aux, SEQ(CHAR('a'),SEQ(CHAR('b'), BIG_aux))) |
|
127 |
|
128 size(ders("".toList, BIG)) // 13 |
|
129 size(ders("ab".toList, BIG)) // 51 |
|
130 size(ders("abab".toList, BIG)) // 112 |
|
131 size(ders("ababab".toList, BIG)) // 191 |
|
132 size(ders("abababab".toList, BIG)) // 288 |
|
133 size(ders("ababababab".toList, BIG)) // 403 |
|
134 size(ders("abababababab".toList, BIG)) // 536 |
|
135 |
|
136 |
|
137 size(ders(("ab" * 200).toList, BIG)) // 366808 |
|
138 |