--- a/data.sty Tue Oct 04 12:00:23 2016 +0100
+++ b/data.sty Tue Oct 04 14:30:08 2016 +0100
@@ -99,20 +99,26 @@
%% re1.scala: example (a*)* b
\begin{filecontents}{re1a.data}
-1 0.00063
-501 0.17873
-1001 0.38154
-1501 0.31391
-2001 0.44642
-2501 0.68948
-3001 0.96061
-3501 1.23515
-4001 1.77727
-4501 2.20843
-5001 2.54629
-5501 3.07348
-6001 3.63944
-6501 4.67416
+1 0.00003
+2 0.00002
+3 0.00004
+4 0.00023
+5 0.00012
+6 0.00016
+7 0.00036
+8 0.00100
+9 0.00158
+10 0.00271
+11 0.00420
+12 0.01034
+13 0.01629
+14 0.03469
+15 0.08800
+16 0.12071
+17 0.27164
+18 0.53962
+19 1.05733
+20 2.34022
\end{filecontents}
%% re2.scala example a?{n} a{n}
@@ -133,96 +139,98 @@
%% re2.scala: 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
+1 0.00004
+2 0.00003
+3 0.00004
+4 0.00014
+5 0.00017
+6 0.00029
+7 0.00046
+8 0.00084
+9 0.00137
+10 0.00203
+11 0.00379
+12 0.00783
+13 0.01583
+14 0.04725
+15 0.06672
+16 0.16228
+17 0.25493
+18 0.53676
+19 1.09052
+20 2.56922
\end{filecontents}
%% re3.scala: example a?{n} a{n}
\begin{filecontents}{re3.data}
-1 0.001605
-501 0.131066
-1001 0.057885
-1501 0.136875
-2001 0.176238
-2501 0.254363
-3001 0.37262
-3501 0.500946
-4001 0.638384
-4501 0.816605
-5001 1.00491
-5501 1.232505
-6001 1.525672
-6501 1.757502
-7001 2.092784
-7501 2.429224
-8001 2.803037
-8501 3.463045
-9001 3.609
-9501 4.081504
-10001 4.54569
-10501 6.17789
-11001 6.77242
-11501 7.95864
+1 0.00005
+1001 0.63505
+2001 2.53029
+3001 5.72804
+4001 9.94246
+5001 15.52770
+6001 22.44126
+7001 30.86867
+8001 39.32242
+9001 48.96998
\end{filecontents}
%% re3.scala: example (a*)* b
\begin{filecontents}{re3a.data}
-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
+1 0.00014
+500001 2.61059
+1000001 5.42773
+1500001 8.02603
+2000001 10.49844
+2500001 13.34234
+3000001 16.17491
+3500001 19.11650
+4000001 21.66151
+4500001 24.85496
+5000001 28.52113
+5500001 28.54548
+6000001 32.39523
+6500001 45.13486
+7000001 54.15018
+7500001 71.32218
\end{filecontents}
%% re4.scala 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
+1 0.01399
+500001 1.43645
+1000001 2.59394
+1500001 4.07990
+2000001 5.22473
+2500001 6.41714
+3000001 7.60118
+3500001 9.02056
+4000001 10.50393
+4500001 11.56631
+5000001 13.72020
+5500001 15.09634
+6000001 29.26990
+6500001 33.41039
+7000001 39.06532
\end{filecontents}
%% re4.scala 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
+500001 2.57302
+1000001 5.58966
+1500001 8.16531
+2000001 10.85055
+2500001 13.42080
+3000001 16.08712
+3500001 18.58433
+4000001 21.23788
+4500001 23.72459
+5000001 27.47479
+5500001 31.85240
+6000001 37.12461
+6500001 39.90294
+7000001 53.50961
\end{filecontents}
\begin{filecontents}{nfa.data}
--- a/progs/re2.scala Tue Oct 04 12:00:23 2016 +0100
+++ b/progs/re2.scala Tue Oct 04 14:30:08 2016 +0100
@@ -56,14 +56,15 @@
//test: (a?{n}) (a{n})
-for (i <- 1 to 1101 by 100) {
+for (i <- 1 to 1001 by 100) {
println(i + " " + "%.5f".format(time_needed(2, matches(EVIL1(i), "a" * i))))
}
-for (i <- 1 to 1101 by 100) {
+for (i <- 1 to 1001 by 100) {
println(i + " " + "%.5f".format(time_needed(2, matches(EVIL1(i), "a" * i))))
}
+
//test: (a*)* b
for (i <- 1 to 20) {
println(i + " " + "%.5f".format(time_needed(2, matches(EVIL2, "a" * i))))
--- a/progs/re3.scala Tue Oct 04 12:00:23 2016 +0100
+++ b/progs/re3.scala Tue Oct 04 14:30:08 2016 +0100
@@ -80,20 +80,20 @@
//test: (a?{n}) (a{n})
-for (i <- 1 to 10001 by 1000) {
+for (i <- 1 to 9001 by 1000) {
println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL1(i), "a" * i))))
}
-for (i <- 1 to 10001 by 1000) {
+for (i <- 1 to 9001 by 1000) {
println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL1(i), "a" * i))))
}
//test: (a*)* b
-for (i <- 1 to 7500001 by 500000) {
+for (i <- 1 to 7000001 by 500000) {
println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL2, "a" * i))))
}
-for (i <- 1 to 7500001 by 500000) {
+for (i <- 1 to 7000001 by 500000) {
println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL2, "a" * i))))
}
--- a/progs/re4.scala Tue Oct 04 12:00:23 2016 +0100
+++ b/progs/re4.scala Tue Oct 04 14:30:08 2016 +0100
@@ -29,7 +29,7 @@
case SEQ(r1, r2) =>
if (nullable(r1)) ALT(SEQ(der(c, r1), r2), der(c, r2))
else SEQ(der(c, r1), r2)
- case STAR(r) => SEQ(der(c, r), STAR(r))
+ case STAR(r1) => SEQ(der(c, r1), STAR(r1))
case NTIMES(r, i) =>
if (i == 0) ZERO else SEQ(der(c, r), NTIMES(r, i - 1))
}
@@ -74,7 +74,7 @@
def OPT(r: Rexp) = ALT(r, ONE)
def EVIL1(n: Int) = SEQ(NTIMES(OPT(CHAR('a')), n), NTIMES(CHAR('a'), n))
-val EVIL2 = SEQ(STAR(CHAR('a')), CHAR('b'))
+val EVIL2 = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))
def time_needed[T](i: Int, code: => T) = {
@@ -85,14 +85,23 @@
}
// warmup
-val i = 5000
-println(i + " " + "%.5f".format(time_needed(10, matcher(EVIL1(i), "a" * i))))
+//test: (a?{n}) (a{n})
+for (i <- 1 to 7000001 by 500000) {
+ println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL1(i), "a" * i))))
+}
-for (i <- 1 to 7000001 by 1000000) {
+for (i <- 1 to 7000001 by 500000) {
println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL1(i), "a" * i))))
}
-for (i <- 1 to 7500001 by 500000) {
+//test: (a*)* b
+for (i <- 1 to 7000001 by 500000) {
println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL2, "a" * i))))
}
+for (i <- 1 to 7000001 by 500000) {
+ println(i + " " + "%.5f".format(time_needed(2, matcher(EVIL2, "a" * i))))
+}
+
+
+