afl-material: comparison handouts/ho02.tex

equal deleted inserted replaced

-:065ca01b62ae
+:4ae59fd3b174
 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}
-Plots: $a^{?\{n\}} \cdot a^{\{n\}}$ and strings $\underbrace{a\ldots a}_{n}$\\
+Graphs: $a^{?\{n\}} \cdot a^{\{n\}}$ and strings $\underbrace{a\ldots a}_{n}$\\
 \begin{tabular}{@{}cc@{}}
 \begin{tikzpicture}
 \begin{axis}[
 xlabel={$n$},
 x label style={at={(1.05,0.0)}},
 ytick={0,5,...,30},
 scaled ticks=false,
 axis lines=left,
 width=6.5cm,
 height=5cm]
-\addplot[green,mark=square*,mark options={fill=white}] table {re2b.data};
+\addplot[green,mark=square*,mark options={fill=white}] table {re2.data};
 \addplot[black,mark=square*,mark options={fill=white}] table {re3.data};
 \end{axis}
 \end{tikzpicture}
 \end{tabular}
 \end{center}
 \begin{center}
-Plots: $(a^*)^* \cdot b$ and strings $\underbrace{a\ldots a}_{n}$
+Graphs: $(a^*)^* \cdot b$ and strings $\underbrace{a\ldots a}_{n}$
 \begin{tabular}{@{}cc@{}}
 \begin{tikzpicture}
 \begin{axis}[
 xlabel={$n$},
 x label style={at={(1.05,0.0)}},
 width=5cm,
 height=5cm,
 legend entries={Java},
 legend pos=north west,
 legend cell align=left]
-\addplot[blue,mark=*, mark options={fill=white}] table {re-java.data};
+\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
 \end{axis}
 \end{tikzpicture}
 &
 \begin{tikzpicture}
 \begin{axis}[
 ytick={0,5,...,30},
 scaled ticks=false,
 axis lines=left,
 width=6.5cm,
 height=5cm]
-\addplot[green,mark=square*,mark options={fill=white}] table {re2b.data};
+\addplot[green,mark=square*,mark options={fill=white}] table {re2.data};
 \addplot[black,mark=square*,mark options={fill=white}] table {re3.data};
 \end{axis}
 \end{tikzpicture}
 \end{tabular}
 \end{center}\medskip
 It seems our algorithm is doing rather well in comparison:
 \begin{center}
 \begin{tikzpicture}
 \begin{axis}[
-title={Plot: $(a^*)^* \cdot b$ and strings $\underbrace{a\ldots a}_{n}$},
+title={Graph: $(a^*)^* \cdot b$ and strings $\underbrace{a\ldots a}_{n}$},
 xlabel={$n$},
 x label style={at={(1.05,0.0)}},
 ylabel={time in secs},
 enlargelimits=false,
-xtick={0,500,...,4000},
+xtick={0,1000,...,6500},
-xmax=4100,
+xmax=6800,
 ytick={0,5,...,30},
+ymax=34,
 scaled ticks=false,
 axis lines=left,
-width=10cm,
+width=8cm,
 height=4.5cm,
 legend entries={Java,Scala V1},
 legend pos=north east,
 legend cell align=left]
-\addplot[blue,mark=*, mark options={fill=white}]
+\addplot[cyan,mark=*, mark options={fill=white}]
 table {re-java.data};
 \addplot[red,mark=triangle*,mark options={fill=white}]
-table {re2c.data};
+table {re1a.data};
 \end{axis}
 \end{tikzpicture}
 \end{center}
 \noindent
-This is no error: it hardly takes more than half a second for
+This is not an error: it hardly takes more than half a second for
-strings up to the length of 4000. After that we receive a
+strings up to the length of 6500. After that we receive a
 StackOverflow exception, but still\ldots
 For running the algorithm with our first example, the evil
 regular expression $a^?{}^{\{n\}}a^{\{n\}}$, we need to implement
 the optional regular expression and the exactly $n$-times
 Ooops\ldots
 \begin{center}
 \begin{tikzpicture}
 \begin{axis}[
-title={Plot: $a^{?\{n\}} \cdot a^{\{n\}}$ and strings $\underbrace{a\ldots a}_{n}$},
+title={Graph: $a^{?\{n\}} \cdot a^{\{n\}}$ and strings $\underbrace{a\ldots a}_{n}$},
 xlabel={$n$},
 x label style={at={(1.05,0.0)}},
 ylabel={time in secs},
 enlargelimits=false,
 xtick={0,5,...,30},
-xmax=30,
+xmax=32,
 ytick={0,5,...,30},
 scaled ticks=false,
 axis lines=left,
 width=6cm,
 height=5cm,
 legend entries={Python,Ruby,Scala V1},
 legend pos=outer north east,
-legend cell align=left
+legend cell align=left]
-]
 \addplot[blue,mark=*, mark options={fill=white}]
 table {re-python.data};
 \addplot[brown,mark=pentagon*, mark options={fill=white}]
 table {re-ruby.data};
 \addplot[red,mark=triangle*,mark options={fill=white}]
 effect?
 \begin{center}
 \begin{tikzpicture}
 \begin{axis}[
-title={Plot: $a^{?\{n\}} \cdot a^{\{n\}}$ and strings $\underbrace{a\ldots a}_{n}$},
+title={Graph: $a^{?\{n\}} \cdot a^{\{n\}}$ and strings $\underbrace{a\ldots a}_{n}$},
 xlabel={$n$},
 x label style={at={(1.01,0.0)}},
 ylabel={time in secs},
 enlargelimits=false,
 xtick={0,100,...,1000},
 \addplot[brown,mark=pentagon*, mark options={fill=white}]
 table {re-ruby.data};
 \addplot[red,mark=triangle*,mark options={fill=white}]
 table {re1.data};
 \addplot[green,mark=square*,mark options={fill=white}]
-table {re2b.data};
+table {re2.data};
 \end{axis}
 \end{tikzpicture}
 \end{center}
 \noindent Now we are talking business! The modified matcher
 \end{figure}
 \begin{center}
 \begin{tikzpicture}
 \begin{axis}[
-title={Plot: $a^{?\{n\}} \cdot a^{\{n\}}$ and strings $\underbrace{a\ldots a}_{n}$},
+title={Graph: $a^{?\{n\}} \cdot a^{\{n\}}$ and strings $\underbrace{a\ldots a}_{n}$},
 xlabel={$n$},
 x label style={at={(1.04,0.0)}},
 ylabel={time in secs},
 enlargelimits=false,
 xtick={0,2000,...,12000},
 xmax=13000,
 ytick={0,5,...,30},
+ymax=12,
 scaled ticks=false,
 axis lines=left,
 width=9cm,
 height=5cm,
-legend entries={Scala V2,Scala V3}]
+legend entries={Scala V2,Scala V3},
-\addplot[green,mark=square*,mark options={fill=white}] table {re2b.data};
+legend pos=outer north east,
+legend cell align=left]
+\addplot[green,mark=square*,mark options={fill=white}] table {re2.data};
 \addplot[black,mark=square*,mark options={fill=white}] table {re3.data};
 \end{axis}
 \end{tikzpicture}
 \end{center}
+\noindent
+To reacap, Python and Ruby needed approximately 30 seconds to match
+a string of 28 \texttt{a}s and the regular expression $a^{?\{n\}} \cdot a^{\{n\}}$.
+We need a third of this time to do the same with strings up to 12,000 \texttt{a}s.
+Similarly, Java needed 30 seconds to find out the regular expression
+$(a^*)^* \cdot b$ does not match the string of 28 \texttt{a}s. We can do
+the same in approximately 5 seconds for strings of 6000000 \texttt{a}s:
 \begin{center}
 \begin{tikzpicture}
 \begin{axis}[
-title={Plot: $(a^*)^* \cdot b$ and strings $\underbrace{a\ldots a}_{n}$},
+title={Graph: $(a^*)^* \cdot b$ and strings $\underbrace{a\ldots a}_{n}$},
 xlabel={$n$},
 x label style={at={(1.09,0.0)}},
 ylabel={time in secs},
 enlargelimits=false,
-%xtick={0,1e+6,...,6e+6},
+xmax=7700000,
-xmax=6200000,
 ytick={0,5,...,30},
-ymax=33,
+ymax=15,
-scaled ticks=false,
+%scaled ticks=false,
 axis lines=left,
 width=9cm,
 height=5cm,
-legend entries={Scala V3}]
+legend entries={Scala V2, Scala V3},
+legend pos=outer north east,
+legend cell align=left]
+\addplot[green,mark=square*,mark options={fill=white}] table {re2a.data};
 \addplot[black,mark=square*,mark options={fill=white}] table {re3a.data};
 \end{axis}
 \end{tikzpicture}
 \end{center}
-\section{Epilogue}
+\subsection*{Epilogue}
-TBD
+(23/Aug/2016) I recently found another place where this algorithm can be
+sped (this idea is not integrated with what is coming next,
+but I present it nonetheless). The idea is to define \texttt{ders}
+not such that it iterates the derivative character-by-character, but
+in bigger chunks. The resulting code for \texttt{ders2} looks as
+follows:
+\lstinputlisting[numbers=none]{../progs/app52.scala}
+\noindent
+I have not fully understood why this version is much faster,
+but it seems it is a combination of the clauses for \texttt{ALT}
+and \texttt{SEQ}. In the latter case we call \texttt{der} with
+a single character and this potentially produces an alternative.
+The derivative of such an alternative can then be more effeciently
+calculated by \texttt{ders2} since it pushes a whole string
+under an \texttt{ALT}. The numbers are that in the second case
+$(a^*)^* \cdot b$ both versions are pretty much the same, but in the
+first case $a^{?\{n\}} \cdot a^{\{n\}}$ the improvement gives
+another factor of 100 speedup. Nice!
+\begin{center}
+\begin{tabular}{cc}
+\begin{tikzpicture}
+\begin{axis}[
+title={Graph: $a^{?\{n\}} \cdot a^{\{n\}}$ and strings $\underbrace{a\ldots a}_{n}$},
+xlabel={$n$},
+x label style={at={(1.04,0.0)}},
+ylabel={time in secs},
+enlargelimits=false,
+xmax=7100000,
+ytick={0,5,...,30},
+ymax=33,
+%scaled ticks=false,
+axis lines=left,
+width=5cm,
+height=5cm,
+legend entries={Scala V3, Scala V4},
+legend pos=north west]
+\addplot[black,mark=square*,mark options={fill=white}] table {re3.data};
+\addplot[purple,mark=square*,mark options={fill=white}] table {re4.data};
+\end{axis}
+\end{tikzpicture}
+&
+\begin{tikzpicture}
+\begin{axis}[
+title={Graph: $(a^*)^* \cdot b$ and strings $\underbrace{a\ldots a}_{n}$},
+xlabel={$n$},
+x label style={at={(1.09,0.0)}},
+ylabel={time in secs},
+enlargelimits=false,
+xmax=8100000,
+ytick={0,5,...,30},
+ymax=33,
+%scaled ticks=false,
+axis lines=left,
+width=5cm,
+height=5cm,
+legend entries={Scala V3, Scala V4},
+legend pos=north west]
+\addplot[black,mark=square*,mark options={fill=white}] table {re3a.data};
+\addplot[purple,mark=square*,mark options={fill=white}] table {re4a.data};
+\end{axis}
+\end{tikzpicture}
+\end{tabular}
+\end{center}
 \section*{Proofs}
 You might not like doing proofs. But they serve a very

changeset 415	4ae59fd3b174
parent 414	065ca01b62ae
child 416	357c395ae838