added some timing and size tests when doing the derivatives
authorChristian Urban <urbanc@in.tum.de>
Fri, 01 Feb 2019 14:31:38 +0000
changeset 299 cae7eab03018
parent 298 db329a4d2bc0
child 300 b7987014fed8
added some timing and size tests when doing the derivatives
exps/both.scala
--- a/exps/both.scala	Thu Jan 31 09:07:50 2019 +0000
+++ b/exps/both.scala	Fri Feb 01 14:31:38 2019 +0000
@@ -225,6 +225,12 @@
   case r => (r, F_ID)
 }
 
+def ders_simp(s: List[Char], r: Rexp) : Rexp = s match {
+  case Nil => r
+  case c::s => ders_simp(s, simp(der(c, r))._1)
+}
+
+
 def lex_simp(r: Rexp, s: List[Char]) : Val = s match {
   case Nil => if (nullable(r)) mkeps(r) else throw new Exception("Not matched")
   case c::cs => {
@@ -354,12 +360,6 @@
 }
 
 
-def ders (s: List[Char], r: Rexp) : Rexp = s match {
-  case Nil => r
-  case c::s => ders(s, der(c, r))
-}
-
-
 // derivative w.r.t. a string (iterates bder)
 @tailrec
 def bders (s: List[Char], r: ARexp) : ARexp = s match {
@@ -403,33 +403,14 @@
 
 
 def blexing_simp(r: Rexp, s: String) : Val = 
-  decode(r, blex_simp(internalise(r), s.toList))
+ decode(r, blex_simp(internalise(r), s.toList))
+
 
 def btokenise_simp(r: Rexp, s: String) = env(blexing_simp(r, s)).map(esc2)
 
-//----------------------------------------------------------------------------
-// This bsimp is the original slow one
-/*
-def bsimp(r: ARexp): ARexp = r match {
-  case ASEQ(bs1, r1, r2) => (bsimp(r1), bsimp(r2)) match {
-      case (AZERO, _) => AZERO
-      case (_, AZERO) => AZERO
-      case (AONE(bs2), r2s) => fuse(bs1 ++ bs2, r2s)
-      case (r1s, r2s) => ASEQ(bs1, r1s, r2s)
-  }
-  case AALTS(bs1, rs) => {
-    distinctBy(flats(rs.map(bsimp)), erase) match {
-      case Nil => AZERO
-      case s :: Nil => fuse(bs1, s)
-      case rs => AALTS(bs1, rs)  
-    }
-  }
-  case r => r
-}
-*/
 
 
-//----------------------------------------------------------------------------
+
 //   Testing
 //============
 
@@ -441,6 +422,13 @@
   //result
 }
 
+def timeR[T](code: => T) = {
+  val start = System.nanoTime()
+  val result = code
+  val end = System.nanoTime()
+  (result, (end - start)/1.0e9)
+}
+
 //size: of a Aregx for testing purposes 
 def size(r: Rexp) : Int = r match {
   case ZERO => 1
@@ -449,6 +437,7 @@
   case SEQ(r1, r2) => 1 + size(r1) + size(r2)
   case ALTS(rs) => 1 + rs.map(size).sum
   case STAR(r) => 1 + size(r)
+  case RECD(_, r) => size(r)
 }
 
 def asize(a: ARexp) = size(erase(a))
@@ -529,12 +518,36 @@
 println("fib prog tests :")
 println(tokenise_simp(WHILE_REGS, fib_prog))
 println(btokenise_simp(WHILE_REGS, fib_prog))
-println(time(tokenise_simp(WHILE_REGS, fib_prog * 7)))
-println(time(btokenise_simp(WHILE_REGS, fib_prog * 7)))
 println("equal? " + (tokenise_simp(WHILE_REGS, fib_prog) == btokenise_simp(WHILE_REGS, fib_prog)))
 
+for (i <- 1 to 10) {
+  print("Old: " + time(tokenise_simp(WHILE_REGS, fib_prog * i)))
+  println(" Bit: " + time(btokenise_simp(WHILE_REGS, fib_prog * i)))
+}
+
+println("Original " + size(WHILE_REGS))
+println("Size Bit " + asize(bders_simp((fib_prog * 10).toList, internalise(WHILE_REGS))))
+println("Size Old " + size(ders_simp((fib_prog * 10).toList, WHILE_REGS)))
 
 
+println("Internal sizes test OK or strange")
+
+def ders_test(n: Int, s: List[Char], r: Rexp, a: ARexp) : (Rexp, ARexp) = s match {
+  case Nil => (r, a)
+  case c::s => {
+    val (rd, tr) = timeR(simp(der(c, r))._1)
+    val (ad, ta) = timeR(bsimp(bder(c, a)))
+    val trs = f"${tr}%.5f"
+    val tas = f"${ta}%.5f"
+    if (tr < ta) println("Time strange  (step) " + n + "   " + trs + " " + tas + " sizes  " + size(rd) + " " + asize(ad))
+    if (size(rd) < asize(ad)) println("Size strange (step) " + n + "   " + size(rd) + " " + asize(ad))
+    //if (size(rd) >= asize(ad)) println(" Size OK    " + size(rd) + " " + asize(ad))
+    ders_test(n + 1, s, rd, ad)
+  }
+}
+
+val prg = (fib_prog * 10).toList
+ders_test(0, prg, WHILE_REGS, internalise(WHILE_REGS))
 
 
 //testing the two lexings produce the same value
@@ -574,3 +587,6 @@
 
 println("Partial searching: ")
 enum(2, "abc").map(tests(strs(3, "abc"))).toSet
+
+
+