# HG changeset patch # User Christian Urban # Date 1475587808 -3600 # Node ID 028816884f70264b143a64e85beced0c9e3bd1f8 # Parent e14cd32ad497bdb136675be9b1cd692ea1023ba1 updated diff -r e14cd32ad497 -r 028816884f70 data.sty --- 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} diff -r e14cd32ad497 -r 028816884f70 progs/re2.scala --- 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)))) diff -r e14cd32ad497 -r 028816884f70 progs/re3.scala --- 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)))) } diff -r e14cd32ad497 -r 028816884f70 progs/re4.scala --- 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)))) +} + + +