2 \usepackage{../style}

     2 \usepackage{../style}

     3 \usepackage{../langs}

     3 \usepackage{../langs}

     4 \usepackage{../graphics}

     4 \usepackage{../graphics}

     5 \usepackage{../data}

     5 \usepackage{../data}

     6 

     6 

     8 \begin{document}

     8 \begin{document}

     9 

     9 

    10 \section*{Handout 2}

    10 \section*{Handout 2}

    11 

    11 

    12 This lecture is about implementing a more efficient regular

    12 This lecture is about implementing a more efficient regular

    13 expression matcher (the plots on the right)---more efficient

    13 expression matcher (the plots on the right)---more efficient

    14 than the matchers from regular expression libraries in Ruby and

    14 than the matchers from regular expression libraries in Ruby and

    15 Python (the plots on the left). These plots show the running 

    15 Python (the plots on the left). These plots show the running 

    16 time for the evil regular expression $a?^{\{n\}}a^{\{n\}}$.

    16 time for the evil regular expression $a?^{\{n\}}a^{\{n\}}$.

    20 \begin{center}

    20 \begin{center}

    21 \begin{tabular}{@{}cc@{}}

    21 \begin{tabular}{@{}cc@{}}

    22 \begin{tikzpicture}

    22 \begin{tikzpicture}

    23 \begin{axis}[

    23 \begin{axis}[

    24     xlabel={\pcode{a}s},

    24     xlabel={\pcode{a}s},

   421 

   421 

   422 \noindent Running the matcher with the example, we find it is

   422 \noindent Running the matcher with the example, we find it is

   423 slightly worse then the matcher in Ruby and Python.

   423 slightly worse then the matcher in Ruby and Python.

   424 Ooops\ldots

   424 Ooops\ldots

   425 

   425 

   427 \begin{center}

   426 \begin{center}

   428 \begin{tikzpicture}

   427 \begin{tikzpicture}

   429 \begin{axis}[

   428 \begin{axis}[

   430     xlabel={\pcode{a}s},

   429     xlabel={\pcode{a}s},

   431     ylabel={time in secs},

   430     ylabel={time in secs},

   480 \noindent With this we have a constant ``size'' regular

   479 \noindent With this we have a constant ``size'' regular

   481 expression for our running example no matter how large $n$ 

   480 expression for our running example no matter how large $n$ 

   482 is. This means we have to also add cases for $nullable$ and

   481 is. This means we have to also add cases for $nullable$ and

   483 $der$. Does the change have any effect?

   482 $der$. Does the change have any effect?

   484 

   483 

   486 \begin{center}

   484 \begin{center}

   487 \begin{tikzpicture}

   485 \begin{tikzpicture}

   488 \begin{axis}[

   486 \begin{axis}[

   489     xlabel={\pcode{a}s},

   487     xlabel={\pcode{a}s},

   490     ylabel={time in secs},

   488     ylabel={time in secs},

   492     xtick={0,100,...,1000},

   490     xtick={0,100,...,1000},

   493     xmax=1000,

   491     xmax=1000,

   494     ytick={0,5,...,30},

   492     ytick={0,5,...,30},

   495     scaled ticks=false,

   493     scaled ticks=false,

   496     axis lines=left,

   494     axis lines=left,

   498     height=5cm, 

   496     height=5cm, 

   499     legend entries={Python,Ruby,Scala V1,Scala V2},  

   497     legend entries={Python,Ruby,Scala V1,Scala V2},  

   500     legend pos=outer north east,

   498     legend pos=outer north east,

   501     legend cell align=left  

   499     legend cell align=left  

   502 ]

   500 ]

   564 \lstinputlisting{../progs/app6.scala}

   562 \lstinputlisting{../progs/app6.scala}

   565 \caption{The simplification function and modified 

   563 \caption{The simplification function and modified 

   566 \pcode{ders}-function.\label{scala2}}

   564 \pcode{ders}-function.\label{scala2}}

   567 \end{figure}

   565 \end{figure}

   568 

   566 

   570 \begin{center}

   567 \begin{center}

   571 \begin{tikzpicture}

   568 \begin{tikzpicture}

   572 \begin{axis}[

   569 \begin{axis}[

   573     xlabel={\pcode{a}s},

   570     xlabel={\pcode{a}s},

   574     ylabel={time in secs},

   571     ylabel={time in secs},