468 matching and recursion allow us to mimic the mathematical |
468 matching and recursion allow us to mimic the mathematical |
469 definitions very closely.\label{scala1}} |
469 definitions very closely.\label{scala1}} |
470 \end{figure} |
470 \end{figure} |
471 |
471 |
472 |
472 |
473 Remember our second example involving the regular expression |
473 %Remember our second example involving the regular expression |
474 $(a^*)^* \cdot b$ which could not match strings of $n$ \texttt{a}s. |
474 %$(a^*)^* \cdot b$ which could not match strings of $n$ \texttt{a}s. |
475 Java needed around 30 seconds to find this out a string with $n=28$. |
475 %Java needed around 30 seconds to find this out a string with $n=28$. |
476 It seems our algorithm is doing rather well in comparison: |
476 %It seems our algorithm is doing rather well in comparison: |
477 |
477 % |
478 \begin{center} |
478 %\begin{center} |
479 \begin{tikzpicture} |
479 %\begin{tikzpicture} |
480 \begin{axis}[ |
480 %\begin{axis}[ |
481 title={Graph: $(a^*)^* \cdot b$ and strings $\underbrace{a\ldots a}_{n}$}, |
481 % title={Graph: $(a^*)^* \cdot b$ and strings $\underbrace{a\ldots a}_{n}$}, |
482 xlabel={$n$}, |
482 % xlabel={$n$}, |
483 x label style={at={(1.05,0.0)}}, |
483 % x label style={at={(1.05,0.0)}}, |
484 ylabel={time in secs}, |
484 % ylabel={time in secs}, |
485 enlargelimits=false, |
485 % enlargelimits=false, |
486 xtick={0,1000,...,6500}, |
486 % xtick={0,1000,...,6500}, |
487 xmax=6800, |
487 % xmax=6800, |
488 ytick={0,5,...,30}, |
488 % ytick={0,5,...,30}, |
489 ymax=34, |
489 % ymax=34, |
490 scaled ticks=false, |
490 % scaled ticks=false, |
491 axis lines=left, |
491 % axis lines=left, |
492 width=8cm, |
492 % width=8cm, |
493 height=4.5cm, |
493 % height=4.5cm, |
494 legend entries={Java,Scala V1}, |
494 % legend entries={Java,Scala V1}, |
495 legend pos=north east, |
495 % legend pos=north east, |
496 legend cell align=left] |
496 % legend cell align=left] |
497 \addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data}; |
497 %\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data}; |
498 \addplot[red,mark=triangle*,mark options={fill=white}] table {re1a.data}; |
498 %\addplot[red,mark=triangle*,mark options={fill=white}] table {re1a.data}; |
499 \end{axis} |
499 %\end{axis} |
500 \end{tikzpicture} |
500 %\end{tikzpicture} |
501 \end{center} |
501 %\end{center} |
502 |
502 % |
503 \noindent |
503 %\noindent |
504 This is not an error: it hardly takes more than half a second for |
504 %This is not an error: it hardly takes more than half a second for |
505 strings up to the length of 6500. After that we receive a |
505 %strings up to the length of 6500. After that we receive a |
506 StackOverflow exception, but still\ldots |
506 %StackOverflow exception, but still\ldots |
507 |
507 |
508 For running the algorithm with our first example, the evil |
508 For running the algorithm with our first example, the evil |
509 regular expression $a^?{}^{\{n\}}a^{\{n\}}$, we need to implement |
509 regular expression $a^?{}^{\{n\}}a^{\{n\}}$, we need to implement |
510 the optional regular expression and the exactly $n$-times |
510 the optional regular expression and the exactly $n$-times |
511 regular expression. This can be done with the translations |
511 regular expression. This can be done with the translations |
667 title={Graph: $a^{?\{n\}} \cdot a^{\{n\}}$ and strings $\underbrace{a\ldots a}_{n}$}, |
667 title={Graph: $a^{?\{n\}} \cdot a^{\{n\}}$ and strings $\underbrace{a\ldots a}_{n}$}, |
668 xlabel={$n$}, |
668 xlabel={$n$}, |
669 x label style={at={(1.04,0.0)}}, |
669 x label style={at={(1.04,0.0)}}, |
670 ylabel={time in secs}, |
670 ylabel={time in secs}, |
671 enlargelimits=false, |
671 enlargelimits=false, |
672 xtick={0,2000,...,12000}, |
672 xtick={0,3000,...,9000}, |
673 xmax=13000, |
673 xmax=10000, |
674 ytick={0,5,...,30}, |
674 ytick={0,5,...,30}, |
675 ymax=12, |
675 ymax=32, |
676 scaled ticks=false, |
676 scaled ticks=false, |
677 axis lines=left, |
677 axis lines=left, |
678 width=9cm, |
678 width=9cm, |
679 height=5cm, |
679 height=5cm, |
680 legend entries={Scala V2,Scala V3}, |
680 legend entries={Scala V2,Scala V3}, |
754 xmax=7100000, |
754 xmax=7100000, |
755 ytick={0,5,...,30}, |
755 ytick={0,5,...,30}, |
756 ymax=33, |
756 ymax=33, |
757 %scaled ticks=false, |
757 %scaled ticks=false, |
758 axis lines=left, |
758 axis lines=left, |
759 width=5cm, |
759 width=5.5cm, |
760 height=5cm, |
760 height=5cm, |
761 legend entries={Scala V3, Scala V4}, |
761 legend entries={Scala V3, Scala V4}, |
762 legend pos=north west] |
762 legend style={at={(0.1,-0.2)},anchor=north}] |
763 \addplot[black,mark=square*,mark options={fill=white}] table {re3.data}; |
763 \addplot[black,mark=square*,mark options={fill=white}] table {re3.data}; |
764 \addplot[purple,mark=square*,mark options={fill=white}] table {re4.data}; |
764 \addplot[purple,mark=square*,mark options={fill=white}] table {re4.data}; |
765 \end{axis} |
765 \end{axis} |
766 \end{tikzpicture} |
766 \end{tikzpicture} |
767 & |
767 & |
775 xmax=8100000, |
775 xmax=8100000, |
776 ytick={0,5,...,30}, |
776 ytick={0,5,...,30}, |
777 ymax=33, |
777 ymax=33, |
778 %scaled ticks=false, |
778 %scaled ticks=false, |
779 axis lines=left, |
779 axis lines=left, |
780 width=5cm, |
780 width=5.5cm, |
781 height=5cm, |
781 height=5cm, |
782 legend entries={Scala V3, Scala V4}, |
782 legend entries={Scala V3, Scala V4}, |
783 legend pos=north west] |
783 legend style={at={(0.1,-0.2)},anchor=north}] |
784 \addplot[black,mark=square*,mark options={fill=white}] table {re3a.data}; |
784 \addplot[black,mark=square*,mark options={fill=white}] table {re3a.data}; |
785 \addplot[purple,mark=square*,mark options={fill=white}] table {re4a.data}; |
785 \addplot[purple,mark=square*,mark options={fill=white}] table {re4a.data}; |
786 \end{axis} |
786 \end{axis} |
787 \end{tikzpicture} |
787 \end{tikzpicture} |
788 \end{tabular} |
788 \end{tabular} |