equal
deleted
inserted
replaced
156 |
156 |
157 \begin{lstlisting}[xleftmargin=1mm,numbers=none,basicstyle=\ttfamily\small] |
157 \begin{lstlisting}[xleftmargin=1mm,numbers=none,basicstyle=\ttfamily\small] |
158 $ scala-cli --extra-jars re.jar |
158 $ scala-cli --extra-jars re.jar |
159 scala> import M3._ |
159 scala> import M3._ |
160 scala> for (i <- 0 to 5000000 by 500000) { |
160 scala> for (i <- 0 to 5000000 by 500000) { |
161 | println(f"$i: ${time_needed(2, matcher(EVIL, "a" * i))}%.5f secs.") |
161 println(s"$i: ${time_needed(2, matcher(EVIL, "a" * i))}") |
162 | } |
162 } |
163 0: 0.00002 secs. |
163 0: 0.00002 secs. |
164 500000: 0.10608 secs. |
164 500000: 0.10608 secs. |
165 1000000: 0.22286 secs. |
165 1000000: 0.22286 secs. |
166 1500000: 0.35982 secs. |
166 1500000: 0.35982 secs. |
167 2000000: 0.45828 secs. |
167 2000000: 0.45828 secs. |
171 4000000: 0.99149 secs. |
171 4000000: 0.99149 secs. |
172 4500000: 1.15395 secs. |
172 4500000: 1.15395 secs. |
173 5000000: 1.29659 secs. |
173 5000000: 1.29659 secs. |
174 \end{lstlisting}%$ |
174 \end{lstlisting}%$ |
175 |
175 |
|
176 \noindent |
|
177 For this you need to copy the \texttt{time\_needed} function and the \texttt{EVIL} regular |
|
178 expression from the comments given in \texttt{re.scala}. |
176 |
179 |
177 \subsection*{Preliminaries} |
180 \subsection*{Preliminaries} |
178 |
181 |
179 The task is to implement a regular expression matcher that is based on |
182 The task is to implement a regular expression matcher that is based on |
180 derivatives of regular expressions. Most of the functions are defined by |
183 derivatives of regular expressions. Most of the functions are defined by |