148 // the size of the NFA can be large, |
148 // the size of the NFA can be large, |
149 // thus slowing down the breadth-first search |
149 // thus slowing down the breadth-first search |
150 println("Breadth-first search EVIL1 / EVIL2") |
150 println("Breadth-first search EVIL1 / EVIL2") |
151 |
151 |
152 for (i <- 1 to 13) { |
152 for (i <- 1 to 13) { |
153 println(i + ": " + "%.5f".format(time_needed(2, tmatches_nfa(EVIL1(i), "a" * i)))) |
153 println(s"$i: ${"%.5f".format(time_needed(2, tmatches_nfa(EVIL1(i), "a" * i)))}") |
154 } |
154 } |
155 |
155 |
156 for (i <- 1 to 100 by 5) { |
156 for (i <- 1 to 100 by 5) { |
157 println(i + " " + "%.5f".format(time_needed(2, tmatches_nfa(EVIL2, "a" * i)))) |
157 println(s"$i: ${"%.5f".format(time_needed(2, tmatches_nfa(EVIL2, "a" * i)))}") |
158 } |
158 } |
159 |
159 |
160 |
160 |
161 // the backtracking that is needed in depth-first |
161 // the backtracking that is needed in depth-first |
162 // search can be painfully slow |
162 // search can be painfully slow |
163 println("Depth-first search EVIL1 / EVIL2") |
163 println("Depth-first search EVIL1 / EVIL2") |
164 |
164 |
165 for (i <- 1 to 9) { |
165 for (i <- 1 to 9) { |
166 println(i + " " + "%.5f".format(time_needed(2, tmatches_nfa2(EVIL1(i), "a" * i)))) |
166 println(s"$i: ${"%.5f".format(time_needed(2, tmatches_nfa2(EVIL1(i), "a" * i)))}") |
167 } |
167 } |
168 |
168 |
169 for (i <- 1 to 7) { |
169 for (i <- 1 to 7) { |
170 println(i + " " + "%.5f".format(time_needed(2, tmatches_nfa2(EVIL2, "a" * i)))) |
170 println(s"$i: ${"%.5f".format(time_needed(2, tmatches_nfa2(EVIL2, "a" * i)))}") |
171 } |
171 } |
172 |
172 |
173 |
173 |
174 |
174 |
175 // while my thompson->enfa->subset->partial-function-chain |
175 // while my thompson->enfa->subset->partial-function-chain |
177 // (the test below should be much faster with a more direct |
177 // (the test below should be much faster with a more direct |
178 // construction), in general the DFAs can be slow because of |
178 // construction), in general the DFAs can be slow because of |
179 // the state explosion in the subset construction |
179 // the state explosion in the subset construction |
180 |
180 |
181 for (i <- 1 to 7) { |
181 for (i <- 1 to 7) { |
182 println(i + ": " + "%.5f".format(time_needed(2, tmatches_dfa(EVIL1(i), "a" * i)))) |
182 println(s"$i: ${"%.5f".format(time_needed(2, tmatches_dfa(EVIL1(i), "a" * i)))}") |
183 } |
183 } |
184 |
184 |
185 for (i <- 1 to 100 by 5) { |
185 for (i <- 1 to 100 by 5) { |
186 println(i + " " + "%.5f".format(time_needed(2, tmatches_dfa(EVIL2, "a" * i)))) |
186 println(s"$i: ${"%.5f".format(time_needed(2, tmatches_dfa(EVIL2, "a" * i)))}") |
187 } |
187 } |
188 |
188 |
189 |
189 |
190 |
190 |
191 |
191 |