--- a/data.sty Mon Aug 22 23:05:43 2016 +0200
+++ b/data.sty Tue Aug 23 12:26:13 2016 +0200
@@ -71,7 +71,7 @@
28 29.81185
\end{filecontents}
-
+%% Scala V1, example a?{n} a{n}
\begin{filecontents}{re1.data}
1 0.00179
2 0.00011
@@ -96,59 +96,64 @@
21 21.46013
\end{filecontents}
-\begin{filecontents}{re2a.data}
-1 0.00227
-5 0.00027
-10 0.00075
-15 0.00178
-20 0.00102
-25 0.00028
-30 0.00040
-35 0.00052
-40 0.00075
-45 0.00125
-50 0.00112
-55 0.00099
-60 0.00113
-65 0.00137
-70 0.00170
+%% Scala V1, example (a*)* b
+\begin{filecontents}{re1a.data}
+1 0.00013
+501 0.03610
+1001 0.08543
+1501 0.06424
+2001 0.11329
+2501 0.19428
+3001 0.31500
+3501 0.37748
+4001 0.49636
+4501 0.63803
+5001 0.75320
+5501 0.92438
+6001 1.01979
+6501 1.21709
\end{filecontents}
-\begin{filecontents}{re2b.data}
-1 0.00020
-51 0.00080
-101 0.00678
-151 0.01792
-201 0.04815
-251 0.09648
-301 0.23195
-351 0.52646
-401 0.96277
-451 1.57726
-501 2.00166
-551 2.98341
-601 4.81181
-651 6.57054
-701 9.73973
-751 14.25762
-801 14.80760
-851 19.60958
-901 25.43550
-951 31.96038
+%% Scala V2, example a?{n} a{n}
+\begin{filecontents}{re2.data}
+1 0.00004
+51 0.00079
+101 0.00752
+151 0.02008
+201 0.04462
+251 0.07715
+301 0.13366
+351 0.21700
+401 0.34163
+451 0.47499
+501 0.65810
+551 0.88666
+601 1.17030
+651 1.51570
+701 1.91133
+751 2.38194
+801 3.10061
+851 4.35828
+901 4.73774
+951 6.05984
+1001 6.68179
\end{filecontents}
-\begin{filecontents}{re2c.data}
-1 0.00070
-501 0.02137
-1001 0.04070
-1501 0.08710
-2001 0.14441
-2501 0.21303
-3001 0.33987
-3501 0.43522
-4001 0.55873
+%% Scala V2, example (a*)* b
+\begin{filecontents}{re2a.data}
+1 0.00009
+501 0.02582
+1001 0.03406
+1501 0.07891
+2001 0.14417
+2501 0.22065
+3001 0.33145
+3501 0.44883
+4001 0.63173
+4501 0.81166
\end{filecontents}
+%% Scala V4, example a?{n} a{n}
\begin{filecontents}{re3.data}
1 0.001605
501 0.131066
@@ -176,20 +181,56 @@
11501 7.95864
\end{filecontents}
+%% Scala V4, example (a*)* b
\begin{filecontents}{re3a.data}
-1 0.00006
-500001 0.12975
-1000001 0.38887
-1500001 0.61373
-2000001 0.78268
-2500001 0.98069
-3000001 1.41858
-3500001 1.68450
-4000001 1.84533
-4500001 1.91059
-5000001 1.98881
-5500001 2.66755
-6000001 3.16683
+1 0.00015
+500001 0.16143
+1000001 0.39022
+1500001 0.69623
+2000001 0.92665
+2500001 1.04422
+3000001 1.31200
+3500001 1.51645
+4000001 1.85757
+4500001 1.85903
+5000001 2.01376
+5500001 2.57703
+6000001 4.70017
+6500001 8.62478
+7000001 13.10504
+7500001 17.97648
+\end{filecontents}
+
+%% Scala V5, example a?{n} a{n}
+\begin{filecontents}{re4.data}
+1 0.00007
+1000001 0.65112
+2000001 1.25011
+3000001 1.34581
+4000001 1.68338
+5000001 4.15276
+6000001 13.86084
+7000001 26.39926
+\end{filecontents}
+
+%% Scala V5, example (a*)* b
+\begin{filecontents}{re4a.data}
+1 0.00015
+500001 0.18391
+1000001 0.53715
+1500001 0.72122
+2000001 1.00681
+2500001 1.46824
+3000001 1.77297
+3500001 2.09406
+4000001 2.32992
+4500001 3.54669
+5000001 4.40195
+5500001 3.41926
+6000001 7.32595
+6500001 12.27531
+7000001 19.29151
+7500001 26.28967
\end{filecontents}
\begin{filecontents}{nfa.data}
Binary file handouts/ho01.pdf has changed
--- a/handouts/ho01.tex Mon Aug 22 23:05:43 2016 +0200
+++ b/handouts/ho01.tex Tue Aug 23 12:26:13 2016 +0200
@@ -24,7 +24,7 @@
%% emacs regexes
%% https://www.gnu.org/software/emacs/manual/html_node/elisp/Regular-Expressions.html
-%% reasons for a new prgramming language
+%% reasons for a new prgramming language
%% http://beautifulracket.com
\begin{document}
@@ -182,13 +182,17 @@
are many libraries implementing regular expressions. I am sure
you have come across them before (remember PRA?). Why on earth
then is there any interest in studying them again in depth in
-this module? Well, one answer is in the following graph about
-regular expression matching in Python and in Ruby.
+this module? Well, one answer is in the following two graphs about
+regular expression matching in Python, Ruby and Java.
\begin{center}
+\begin{tabular}{@{}cc@{}}
\begin{tikzpicture}
\begin{axis}[
- xlabel={strings of {\tt a}s},
+ title={Graph: $\texttt{a?\{n\}\,a{\{n\}}}$ and strings
+ $\underbrace{\texttt{a}\ldots \texttt{a}}_{n}$},
+ xlabel={$n$},
+ x label style={at={(1.05,0.0)}},
ylabel={time in secs},
enlargelimits=false,
xtick={0,5,...,30},
@@ -197,7 +201,7 @@
ytick={0,5,...,30},
scaled ticks=false,
axis lines=left,
- width=7cm,
+ width=5.5cm,
height=4.5cm,
legend entries={Python,Ruby},
legend pos=north west,
@@ -208,17 +212,43 @@
table {re-ruby.data};
\end{axis}
\end{tikzpicture}
+&
+\begin{tikzpicture}
+\begin{axis}[
+ title={Graph: $\texttt{(a*)*\,b}$ and strings
+ $\underbrace{\texttt{a}\ldots \texttt{a}}_{n}$},
+ xlabel={$n$},
+ x label style={at={(1.05,0.0)}},
+ ylabel={time in secs},
+ enlargelimits=false,
+ xtick={0,5,...,30},
+ xmax=33,
+ ymax=35,
+ ytick={0,5,...,30},
+ scaled ticks=false,
+ axis lines=left,
+ width=5.5cm,
+ height=4.5cm,
+ legend entries={Java},
+ legend pos=north west,
+ legend cell align=left]
+\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
+\end{axis}
+\end{tikzpicture}
+\end{tabular}
\end{center}
-\noindent This graph shows that Python needs approximately 29
+\noindent This first graph shows that Python needs approximately 29
seconds for finding out whether a string of 28 \texttt{a}s
-matches the regular expression \texttt{[a?]\{28\}[a]\{28\}}.
+matches the regular expression \texttt{a?\{28\}\,a\{28\}}.
Ruby is even slightly worse.\footnote{In this example Ruby
uses the slightly different regular expression
\texttt{a?a?a?...a?a?aaa...aa}, where the \texttt{a?} and
\texttt{a} each occur $n$ times. More such test cases can be
-found at \url{http://www.computerbytesman.com/redos/}.}
-Admittedly, this regular expression is carefully chosen to
+found at \url{http://www.computerbytesman.com/redos/}.} Simlarly, Java needs approximately
+30 seconds to find out that the regular expression $\texttt{(a*)*\,b}$
+does not match strings of 28 \texttt{a}s.
+Admittedly, these regular expressions are carefully chosen to
exhibit this exponential behaviour, but similar ones occur
more often than one wants in ``real life''. For example, on 20
July 2016 a similar regular expression brought the webpage
@@ -229,17 +259,17 @@
\end{center}
\noindent
-Such troublesome regular expressions are sometimes called
-\emph{evil regular expressions} because they have the
-potential to make regular expression matching engines to
-topple over, like in Python and Ruby. The problem with evil
-regular expressions is that they can have some serious
-consequences, for example, if you use them in your
-web-application. The reason is that hackers can look for these
-instances where the matching engine behaves badly and then
-mount a nice DoS-attack against your application. These
-attacks are already have their own name: \emph{Regular
-Expression Denial of Service Attacks (ReDoS)}.
+Such troublesome regular expressions are sometimes called \emph{evil
+ regular expressions} because they have the potential to make regular
+expression matching engines to topple over, like in Python, Ruby and
+Java. This `toopling over' is also sometimes called \emph{catastrophic
+ backtracking}. The problem with evil regular expressions is that
+they can have some serious consequences, for example, if you use them
+in your web-application. The reason is that hackers can look for these
+instances where the matching engine behaves badly and then mount a
+nice DoS-attack against your application. These attacks are already
+have their own name: \emph{Regular Expression Denial of Service
+ Attacks (ReDoS)}.
It will be instructive to look behind the ``scenes'' to find
out why Python and Ruby (and others) behave so badly when
@@ -254,23 +284,53 @@
\begin{center}
\begin{tikzpicture}
\begin{axis}[
- xlabel={strings of \pcode{a}s},
+ title={Graph: $\texttt{a?\{n\}\,a{\{n\}}}$ and strings
+ $\underbrace{\texttt{a}\ldots \texttt{a}}_{n}$},
+ xlabel={$n$},
+ x label style={at={(1.05,0.0)}},
ylabel={time in secs},
enlargelimits=false,
xtick={0,3000,...,12000},
- xmax=12500,
- ymax=35,
- ytick={0,5,...,30},
+ xmax=13000,
+ ymax=12,
+ ytick={0,5,10},
scaled ticks=false,
axis lines=left,
- width=9cm,
- height=4.5cm]
-\addplot[green,mark=square*,mark options={fill=white}] table {re2b.data};
+ width=7cm,
+ height=4.5cm,
+ legend entries={Our Algorithm V1, Our Algorithm V2},
+ legend pos=outer north east]
+\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 And in the case of the regular expression $\texttt{(a*)*\,b}$
+and strings of \texttt{a}s we will beat Java by factor of
+approximately 1,000,000 (note the scale on the $x$-axis).
+
+\begin{center}
+\begin{tikzpicture}
+ \begin{axis}[
+ title={Graph: $\texttt{(a*)*\,b}$ and strings
+ $\underbrace{\texttt{a}\ldots \texttt{a}}_{n}$},
+ xlabel={$n$},
+ x label style={at={(1.05,0.0)}},
+ ylabel={time in secs},
+ enlargelimits=false,
+ ymax=12,
+ ytick={0,5,10},
+ axis lines=left,
+ width=7cm,
+ height=4.5cm,
+ legend entries={Our Algorithm V2},
+ legend pos=outer north east]
+\addplot[black,mark=square*,mark options={fill=white}] table {re3a.data};
+\end{axis}
+\end{tikzpicture}
+\end{center}
+
\subsection*{Basic Regular Expressions}
The regular expressions shown earlier for Scala, we
Binary file handouts/ho02.pdf has changed
--- 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}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/app52.scala Tue Aug 23 12:26:13 2016 +0200
@@ -0,0 +1,9 @@
+def ders2(s: List[Char], r: Rexp) : Rexp = (s, r) match {
+ case (Nil, r) => r
+ case (s, ZERO) => ZERO
+ case (s, ONE) => if (s == Nil) ONE else ZERO
+ case (s, CHAR(c)) => if (s == List(c)) ONE else
+ if (s == Nil) CHAR(c) else ZERO
+ case (s, ALT(r1, r2)) => ALT(ders2(s, r2), ders2(s, r2))
+ case (c::s, r) => ders2(s, der(c, r).simp)
+}
--- a/progs/crawler2.scala Mon Aug 22 23:05:43 2016 +0200
+++ b/progs/crawler2.scala Tue Aug 23 12:26:13 2016 +0200
@@ -33,8 +33,8 @@
}
// starting URL for the crawler
-//val startURL = """http://www.inf.kcl.ac.uk/staff/urbanc"""
-val startURL = """http://www.inf.kcl.ac.uk/staff/urbanc/msc-projects-14.html"""
+val startURL = """http://www.inf.kcl.ac.uk/staff/urbanc"""
+
// can now deal with depth 3 and beyond
crawl(startURL, 2)
--- a/progs/re1.scala Mon Aug 22 23:05:43 2016 +0200
+++ b/progs/re1.scala Tue Aug 23 12:26:13 2016 +0200
@@ -55,7 +55,8 @@
}
// the evil regular expression a?{n} a{n}
-def EVIL(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n))
+def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n))
+val EVIL2 = SEQ(STAR(CHAR('a')), CHAR('b'))
//for measuring time
def time_needed[T](i: Int, code: => T) = {
@@ -66,8 +67,11 @@
}
-for (i <- 1 to 29) {
- println(i + ": " + "%.5f".format(time_needed(1, matches(EVIL(i), "a" * i))))
+for (i <- 1 to 20) {
+ println(i + ": " + "%.5f".format(time_needed(2, matches(EVIL1(i), "a" * i))))
}
+for (i <- 1 to 6502 by 500) {
+ println(i + " " + "%.5f".format(time_needed(2, matches(EVIL2, "a" * i))))
+}
--- a/progs/re2.scala Mon Aug 22 23:05:43 2016 +0200
+++ b/progs/re2.scala Tue Aug 23 12:26:13 2016 +0200
@@ -51,18 +51,18 @@
(end - start)/(i * 1.0e9)
}
-//for (i <- 1 to 100) {
-// println(i + ": " + "%.5f".format(time_needed(1, matches(EVIL1(i), "a" * i))))
-//}
+for (i <- 1 to 100) {
+ println(i + ": " + "%.5f".format(time_needed(1, matches(EVIL1(i), "a" * i))))
+}
//a bit bolder test
-for (i <- 1 to 1000 by 50) {
- println(i + " " + "%.5f".format(time_needed(1, matches(EVIL1(i), "a" * i))))
+for (i <- 1 to 1001 by 50) {
+ println(i + " " + "%.5f".format(time_needed(2, matches(EVIL1(i), "a" * i))))
}
-for (i <- 1 to 4002 by 500) {
- println(i + " " + "%.5f".format(time_needed(4, matches(EVIL2, "a" * i))))
+for (i <- 1 to 4501 by 500) {
+ println(i + " " + "%.5f".format(time_needed(2, matches(EVIL2, "a" * i))))
}
--- a/progs/re4.scala Mon Aug 22 23:05:43 2016 +0200
+++ b/progs/re4.scala Tue Aug 23 12:26:13 2016 +0200
@@ -106,11 +106,11 @@
val i = 5000
println(i + " " + "%.5f".format(time_needed(10, matcher(EVIL1(i), "a" * i))))
-//for (i <- 1 to 10000 by 1000) {
-// println(i + " " + "%.5f".format(time_needed(10, matcher(EVIL1(i), "a" * i))))
-//}
-
-for (i <- 1 to 6000001 by 500000) {
- println(i + " " + "%.5f".format(time_needed(10, matcher(EVIL2, "a" * i))))
+for (i <- 1 to 9001 by 1000) {
+ println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL1(i), "a" * i))))
}
+for (i <- 1 to 7500001 by 500000) {
+ println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL2, "a" * i))))
+}
+
--- a/progs/re5.scala Mon Aug 22 23:05:43 2016 +0200
+++ b/progs/re5.scala Tue Aug 23 12:26:13 2016 +0200
@@ -108,11 +108,11 @@
val i = 5000
println(i + " " + "%.5f".format(time_needed(10, matcher(EVIL1(i), "a" * i))))
-for (i <- 1 to 80000 by 10000) {
+for (i <- 1 to 7000001 by 1000000) {
println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL1(i), "a" * i))))
}
-for (i <- 1 to 10000001 by 1000000) {
+for (i <- 1 to 7500001 by 500000) {
println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL2, "a" * i))))
}