223 width=5.5cm, |
223 width=5.5cm, |
224 height=4.5cm, |
224 height=4.5cm, |
225 legend entries={Python,Ruby}, |
225 legend entries={Python,Ruby}, |
226 legend pos=north west, |
226 legend pos=north west, |
227 legend cell align=left] |
227 legend cell align=left] |
228 \addplot[blue,mark=*, mark options={fill=white}] |
228 \addplot[blue,mark=*, mark options={fill=white}] table {re-python.data}; |
229 table {re-python.data}; |
229 \addplot[brown,mark=triangle*, mark options={fill=white}] table {re-ruby.data}; |
230 \addplot[brown,mark=triangle*, mark options={fill=white}] |
|
231 table {re-ruby.data}; |
|
232 \end{axis} |
230 \end{axis} |
233 \end{tikzpicture} |
231 \end{tikzpicture} |
234 & |
232 & |
235 \begin{tikzpicture} |
233 \begin{tikzpicture} |
236 \begin{axis}[ |
234 \begin{axis}[ |
246 ytick={0,5,...,30}, |
244 ytick={0,5,...,30}, |
247 scaled ticks=false, |
245 scaled ticks=false, |
248 axis lines=left, |
246 axis lines=left, |
249 width=5.5cm, |
247 width=5.5cm, |
250 height=4.5cm, |
248 height=4.5cm, |
251 legend entries={Java}, |
249 legend entries={Python, Java}, |
252 legend pos=north west, |
250 legend pos=north west, |
253 legend cell align=left] |
251 legend cell align=left] |
|
252 \addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data}; |
254 \addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data}; |
253 \addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data}; |
255 \end{axis} |
254 \end{axis} |
256 \end{tikzpicture} |
255 \end{tikzpicture} |
257 \end{tabular} |
256 \end{tabular} |
258 \end{center} |
257 \end{center} |
259 |
258 |
260 \noindent This first graph shows that Python needs approximately 29 |
259 \noindent This first graph shows that Python needs approximately 29 |
261 seconds for finding out whether a string of 28 \texttt{a}s |
260 seconds for finding out whether a string of 28 \texttt{a}s matches the |
262 matches the regular expression \texttt{a?\{28\}\,a\{28\}}. |
261 regular expression \texttt{a?\{28\}\,a\{28\}}. Ruby is even slightly |
263 Ruby is even slightly worse.\footnote{In this example Ruby |
262 worse.\footnote{In this example Ruby uses the slightly different |
264 uses the slightly different regular expression |
263 regular expression \texttt{a?a?a?...a?a?aaa...aa}, where the |
265 \texttt{a?a?a?...a?a?aaa...aa}, where the \texttt{a?} and |
264 \texttt{a?} and \texttt{a} each occur $n$ times. More such test |
266 \texttt{a} each occur $n$ times. More such test cases can be |
265 cases can be found at \url{http://www.computerbytesman.com/redos/}.} |
267 found at \url{http://www.computerbytesman.com/redos/}.} Simlarly, Java needs approximately |
266 Simlarly, Python and Java needs approximately 30 seconds to find out |
268 30 seconds to find out that the regular expression $\texttt{(a*)*\,b}$ |
267 that the regular expression $\texttt{(a*)*\,b}$ does not match strings |
269 does not match strings of 28 \texttt{a}s. |
268 of 28 \texttt{a}s. Admittedly, these regular expressions are |
270 Admittedly, these regular expressions are carefully chosen to |
269 carefully chosen to exhibit this exponential behaviour, but similar |
271 exhibit this exponential behaviour, but similar ones occur |
270 ones occur more often than one wants in ``real life''. For example, on |
272 more often than one wants in ``real life''. For example, on 20 |
271 20 July 2016 a similar regular expression brought the webpage |
273 July 2016 a similar regular expression brought the webpage |
|
274 \href{http://stackexchange.com}{Stack Exchange} to its knees: |
272 \href{http://stackexchange.com}{Stack Exchange} to its knees: |
275 |
273 |
276 \begin{center} |
274 \begin{center} |
277 \url{http://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016} |
275 \url{http://stackstatus.net/post/147710624694/outage-postmortem-july-20-2016} |
278 \end{center} |
276 \end{center} |