equal
deleted
inserted
replaced
1 \documentclass{article} |
1 \documentclass{article} |
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 \usepackage{lstlinebgrd} |
|
7 \definecolor{capri}{rgb}{0.0, 0.75, 1.0} |
7 |
8 |
8 \begin{document} |
9 \begin{document} |
9 \fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017} |
10 \fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017} |
10 |
11 |
11 |
12 |
52 \begin{axis}[ |
53 \begin{axis}[ |
53 xlabel={$n$}, |
54 xlabel={$n$}, |
54 x label style={at={(1.1,0.05)}}, |
55 x label style={at={(1.1,0.05)}}, |
55 ylabel={\small time in secs}, |
56 ylabel={\small time in secs}, |
56 enlargelimits=false, |
57 enlargelimits=false, |
57 xtick={0,3000,...,9000}, |
58 xtick={0,2500,...,11000}, |
58 xmax=10000, |
59 xmax=12000, |
59 ymax=35, |
60 ymax=35, |
60 ytick={0,5,...,30}, |
61 ytick={0,5,...,30}, |
61 scaled ticks=false, |
62 scaled ticks=false, |
62 axis lines=left, |
63 axis lines=left, |
63 width=6.5cm, |
64 width=6.5cm, |
84 ytick={0,5,...,30}, |
85 ytick={0,5,...,30}, |
85 scaled ticks=false, |
86 scaled ticks=false, |
86 axis lines=left, |
87 axis lines=left, |
87 width=5cm, |
88 width=5cm, |
88 height=5cm, |
89 height=5cm, |
89 legend entries={Java}, |
90 legend entries={Java, Python}, |
90 legend pos=north west, |
91 legend pos=north west, |
91 legend cell align=left] |
92 legend cell align=left] |
|
93 \addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data}; |
92 \addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data}; |
94 \addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data}; |
93 \end{axis} |
95 \end{axis} |
94 \end{tikzpicture} |
96 \end{tikzpicture} |
95 & |
97 & |
96 \begin{tikzpicture} |
98 \begin{tikzpicture} |
459 Given the implementation of regular expressions in Scala shown |
461 Given the implementation of regular expressions in Scala shown |
460 in the first lecture and handout, the functions and subfunctions |
462 in the first lecture and handout, the functions and subfunctions |
461 for \pcode{matches} are shown in Figure~\ref{scala1}. |
463 for \pcode{matches} are shown in Figure~\ref{scala1}. |
462 |
464 |
463 \begin{figure}[p] |
465 \begin{figure}[p] |
464 \lstinputlisting{../progs/app5.scala} |
466 \lstinputlisting[numbers=left,linebackgroundcolor= |
|
467 {\ifodd\value{lstnumber}\color{capri!3}\fi}] |
|
468 {../progs/app5.scala} |
465 \caption{Scala implementation of the \textit{nullable} and |
469 \caption{Scala implementation of the \textit{nullable} and |
466 derivative functions. These functions are easy to |
470 derivative functions. These functions are easy to |
467 implement in functional languages, because their built-in pattern |
471 implement in functional languages, because their built-in pattern |
468 matching and recursion allow us to mimic the mathematical |
472 matching and recursion allow us to mimic the mathematical |
469 definitions very closely.\label{scala1}} |
473 definitions very closely.\label{scala1}} |
579 title={Graph: $a^{?\{n\}} \cdot a^{\{n\}}$ and strings $\underbrace{a\ldots a}_{n}$}, |
583 title={Graph: $a^{?\{n\}} \cdot a^{\{n\}}$ and strings $\underbrace{a\ldots a}_{n}$}, |
580 xlabel={$n$}, |
584 xlabel={$n$}, |
581 x label style={at={(1.01,0.0)}}, |
585 x label style={at={(1.01,0.0)}}, |
582 ylabel={time in secs}, |
586 ylabel={time in secs}, |
583 enlargelimits=false, |
587 enlargelimits=false, |
584 xtick={0,100,...,1000}, |
588 xtick={0,200,...,1100}, |
585 xmax=1100, |
589 xmax=1200, |
586 ytick={0,5,...,30}, |
590 ytick={0,5,...,30}, |
587 scaled ticks=false, |
591 scaled ticks=false, |
588 axis lines=left, |
592 axis lines=left, |
589 width=10cm, |
593 width=10cm, |
590 height=5cm, |
594 height=5cm, |
598 \end{axis} |
602 \end{axis} |
599 \end{tikzpicture} |
603 \end{tikzpicture} |
600 \end{center} |
604 \end{center} |
601 |
605 |
602 \noindent Now we are talking business! The modified matcher |
606 \noindent Now we are talking business! The modified matcher |
603 can within 30 seconds handle regular expressions up to |
607 can within 25 seconds handle regular expressions up to |
604 $n = 950$ before a StackOverflow is raised. Recall that Python and Ruby |
608 $n = 1,100$ before a StackOverflow is raised. Recall that Python and Ruby |
605 (and our first version, Scala V1) could only handle $n = 27$ or so in 30 |
609 (and our first version, Scala V1) could only handle $n = 27$ or so in 30 |
606 seconds. There is no change for our second example |
610 seconds. There is no change for our second example |
607 $(a^*)^* \cdot b$---so this is still good. |
611 $(a^*)^* \cdot b$---so this is still good. |
608 |
612 |
609 |
613 |
650 simplification function will be called after every derivation. |
654 simplification function will be called after every derivation. |
651 This additional step removes all the ``junk'' the derivative |
655 This additional step removes all the ``junk'' the derivative |
652 function introduced. Does this improve the speed? You bet!! |
656 function introduced. Does this improve the speed? You bet!! |
653 |
657 |
654 \begin{figure}[p] |
658 \begin{figure}[p] |
655 \lstinputlisting{../progs/app6.scala} |
659 \lstinputlisting[numbers=left,linebackgroundcolor= |
|
660 {\ifodd\value{lstnumber}\color{capri!3}\fi}] |
|
661 {../progs/app6.scala} |
656 \caption{The simplification function and modified |
662 \caption{The simplification function and modified |
657 \texttt{ders}-function; this function now |
663 \texttt{ders}-function; this function now |
658 calls \texttt{der} first, but then simplifies |
664 calls \texttt{der} first, but then simplifies |
659 the resulting derivative regular expressions before |
665 the resulting derivative regular expressions before |
660 building the next derivative, see |
666 building the next derivative, see |