--- a/handouts/ho02.tex Mon Aug 22 23:05:43 2016 +0200
+++ b/handouts/ho02.tex Tue Aug 23 12:26:13 2016 +0200
@@ -24,7 +24,7 @@
\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}[
@@ -64,7 +64,7 @@
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}
@@ -72,7 +72,7 @@
\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}[
@@ -91,7 +91,7 @@
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}
&
@@ -109,7 +109,7 @@
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}
@@ -482,32 +482,33 @@
\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},
- xmax=4100,
+ xtick={0,1000,...,6500},
+ 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
-strings up to the length of 4000. After that we receive a
+This is not an error: it hardly takes more than half a second for
+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
@@ -524,13 +525,13 @@
\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,
@@ -538,7 +539,7 @@
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}]
@@ -584,7 +585,7 @@
\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},
@@ -606,7 +607,7 @@
\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}
@@ -676,7 +677,7 @@
\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},
@@ -684,42 +685,121 @@
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}]
-\addplot[green,mark=square*,mark options={fill=white}] table {re2b.data};
+ legend entries={Scala V2,Scala V3},
+ 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=6200000,
+ xmax=7700000,
ytick={0,5,...,30},
- ymax=33,
- scaled ticks=false,
+ ymax=15,
+ %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}
+
+(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!
-TBD
+\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}