89 @arg(doc = "Test (a*)* b") |
89 @arg(doc = "Test (a*)* b") |
90 @main |
90 @main |
91 def test2() = { |
91 def test2() = { |
92 println("Test (a*)* b") |
92 println("Test (a*)* b") |
93 |
93 |
94 for (i <- 0 to 22 by 2) { |
94 for (i <- 0 to 20 by 2) { |
95 println(f"$i: ${time_needed(1, matcher(EVIL2, "a" * i))}%.5f") |
95 println(f"$i: ${time_needed(1, matcher(EVIL2, "a" * i))}%.5f") |
96 } |
96 } |
97 } |
97 } |
98 |
98 |
99 // the size of a regular expressions - for testing purposes |
99 // the size of a regular expressions - for testing purposes |
106 case STAR(r) => 1 + size(r) |
106 case STAR(r) => 1 + size(r) |
107 case NTIMES(r, _) => 1 + size(r) |
107 case NTIMES(r, _) => 1 + size(r) |
108 } |
108 } |
109 |
109 |
110 // EVIL1(n) has now a constant size, no matter |
110 // EVIL1(n) has now a constant size, no matter |
111 // what n is; also the derivative only grows |
111 // what n is |
112 // moderately |
|
113 |
112 |
114 size(EVIL1(1)) // 7 |
113 size(EVIL1(1)) // 7 |
115 size(EVIL1(3)) // 7 |
114 size(EVIL1(3)) // 7 |
116 size(EVIL1(5)) // 7 |
115 size(EVIL1(5)) // 7 |
117 size(EVIL1(7)) // 7 |
116 size(EVIL1(7)) // 7 |
118 size(EVIL1(20)) // 7 |
117 size(EVIL1(20)) // 7 |
119 |
118 |
|
119 // also the derivative only grows much more |
|
120 // moderately and actually maxes out at size 211 |
|
121 // (for n = 5) |
120 size(ders("".toList, EVIL1(5))) // 7 |
122 size(ders("".toList, EVIL1(5))) // 7 |
121 size(ders("a".toList, EVIL1(5))) // 16 |
123 size(ders("a".toList, EVIL1(5))) // 16 |
122 size(ders("aa".toList, EVIL1(5))) // 35 |
124 size(ders("aa".toList, EVIL1(5))) // 35 |
123 size(ders("aaa".toList, EVIL1(5))) // 59 |
125 size(ders("aaa".toList, EVIL1(5))) // 59 |
124 size(ders("aaaa".toList, EVIL1(5))) // 88 |
126 size(ders("aaaa".toList, EVIL1(5))) // 88 |
125 size(ders("aaaaa".toList, EVIL1(5))) // 122 |
127 size(ders("aaaaa".toList, EVIL1(5))) // 122 |
126 size(ders("aaaaaa".toList, EVIL1(5))) // 151 |
128 size(ders("aaaaaa".toList, EVIL1(5))) // 151 |
127 |
129 |
128 size(ders(("a" * 20).toList, EVIL1(5))) |
130 size(ders(("a" * 20).toList, EVIL1(5))) // 211 |
|
131 size(ders(("a" * 200).toList, EVIL1(5))) // 211 |
|
132 size(ders(("a" * 2000).toList, EVIL1(5))) // 211 |
129 |
133 |
130 // but the size of the derivatives can still grow |
134 // but the size of the derivatives can still grow |
131 // quite dramatically in case of EVIL2: (a*)* b |
135 // quite dramatically in case of EVIL2: (a*)* b |
132 |
136 |
133 size(ders("".toList, EVIL2)) // 5 |
137 size(ders("".toList, EVIL2)) // 5 |