diff -r f7de0915fff2 -r f4818c95a32e handouts/ho02.tex --- a/handouts/ho02.tex Sat Dec 29 10:30:27 2018 +0000 +++ b/handouts/ho02.tex Tue Feb 12 21:23:00 2019 +0000 @@ -6,22 +6,23 @@ \begin{document} -\fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017, 2018} +\fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017, 2018, 2019} \section*{Handout 2 (Regular Expression Matching)} This lecture is about implementing a more efficient regular expression matcher (the plots on the right below)---more efficient than the -matchers from regular expression libraries in Ruby, Python and Java -(the plots on the left). The first pair of plots shows the running time -for the regular expression $(a^*)^*\cdot b$ and strings composed of -$n$ \pcode{a}s (meaning this regular expression actually does not -match the strings). The second pair of plots shows the running time for -the regular expressions $a^?{}^{\{n\}}\cdot a^{\{n\}}$ and strings -also composed of $n$ \pcode{a}s (this time the regular expressions -match the strings). To see the substantial differences in the left -and right plots below, note the different scales of the $x$-axes. +matchers from regular expression libraries in Ruby, Python, JavaScript +and Java (the plots on the left). For this consider some experimental +data: The first pair of plots shows the running time for the +regular expression $(a^*)^*\cdot b$ and strings composed of $n$ +\pcode{a}s (meaning this regular expression actually does not match +the strings). The second pair of plots shows the running time for the +regular expressions $a^?{}^{\{n\}}\cdot a^{\{n\}}$ and strings also +composed of $n$ \pcode{a}s (this time the regular expressions match +the strings). To see the substantial differences in the left and +right plots below, note the different scales of the $x$-axes. \begin{center} @@ -41,11 +42,12 @@ axis lines=left, width=5cm, height=5cm, - legend entries={Java 8, Python}, + legend entries={Java 8, Python, JavaScript}, legend pos=north west, legend cell align=left] \addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data}; \addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data}; +\addplot[red,mark=*, mark options={fill=white}] table {re-js.data}; \end{axis} \end{tikzpicture} &