Changeset 10074

Timestamp:

10/20/13 21:31:41 (11 years ago)

Author:

gkronber

Message:

#2026: finished tree searcher for artifical ant, multiplexer and even parity examples. (+ performance tweak in Artificial Ant.txt)

Location:

branches/HeuristicLab.Problems.GPDL

Files:

• CodeGenerator/BruteForceCodeGen.cs (modified) (10 diffs)
• Examples/Artificial Ant.txt (modified) (2 diffs)

branches/HeuristicLab.Problems.GPDL/CodeGenerator/BruteForceCodeGen.cs

@@ -20 +20 @@
     private string solverTemplate = @"
 namespace ?PROBLEMNAME? {
-  internal static class Grammar {
-    ?GRAMMARCLASSCODE?
-  }
-  internal sealed class PartiallyProcessedSeq {
-    private IEnumerable<string> remaining;
-    private IEnumerable<int> path;
-    public PartiallyProcessedSeq(IEnumerable<string> remaining) : this (Enumerable.Empty<int>(), remaining) {
-    }
-    public PartiallyProcessedSeq(IEnumerable<int> path, IEnumerable<string> remaining) {
-      this.path = path;
-      this.remaining = remaining;
-    }
-
-    public bool MoveNext() {
-      if(!remaining.Any()) return false;
-      else remaining = remaining.Skip(1);
-      return true;
-    }
-
-    public string Current { 
-      get {
-        return remaining.FirstOrDefault();
-      }
-    }
-    public IEnumerable<int> Path {
-      get {
-        return path;
-      }
-    }
-    public IEnumerable<string> Remaining {
-      get {
-        return remaining;
-      }
-    }
-    public override string ToString() {
-      return path.Aggregate("""", (str, p) => str + "" "" + p) + "" >> "" +
-             remaining.Aggregate("""", (str, r) => str + "" "" + r);
-    }
-
-  }
   public sealed class ?IDENT?Solver {
 
@@ -79 +39 @@
     }
 
-    #region path generator (BFS in the grammar to generate solutions)
-    ?PATHGENERATORCODE?
-    #endregion
-
-    private IEnumerable<IEnumerable<int>> GeneratePaths() {
-      var queue = new Queue<PartiallyProcessedSeq>();
-      queue.Enqueue(new PartiallyProcessedSeq(new string[] { Grammar.RootSymbol }));
-
-      while (queue.Count > 0) {
-        var e = queue.Dequeue();
-        var symb = e.Current; // the next symbol to generate paths for
-        // Console.WriteLine(""Out: "" + e);
-
-        var lastSymbol = !e.MoveNext();
-
-        if (Grammar.IsTerminal(symb)) {
-          // generate all paths for the terminal
-          if (lastSymbol) {
-            var pathsForSymb = GeneratePathsFor(symb);
-            if (pathsForSymb.Any()) {
-              foreach (var path in GeneratePathsFor(symb)) {
-                yield return e.Path.Concat(path);
-              }
-            } else {
-              yield return e.Path;
-            }
-          } else {
-            var paths = GeneratePathsFor(symb);
-            if(!paths.Any() || paths.Count() == 1) {
-              yield return e.Path;
-            } else {
-              foreach (var path in paths) {
-                var eAlt = new PartiallyProcessedSeq(e.Path.Concat(path), e.Remaining);
-                queue.Enqueue(eAlt);
-                // Console.WriteLine(""In: "" + eAlt);
-              }
-            }
-          }
+    private class SearchTree {
+      private SearchTree[] subTrees;
+      public bool Done { get; private set; }
+      private int nextAlternative;
+
+      public SearchTree() {
+        Done = false;
+      }
+
+      public SearchTree GetSubtree(int i) {
+        // if (subTrees[i] == null) subTrees[i] = new SearchTree();
+        return subTrees[i];
+      }
+
+      public int GetNextAlternative() {
+        System.Diagnostics.Debug.Assert(IsAlternativeNode);
+        return nextAlternative;
+      }
+
+      public bool IsUninitialized {
+        get { return subTrees == null; }
+      }
+
+      public void SetNumberOfSubtrees(int n) {
+        this.subTrees = new SearchTree[n]; 
+        for(int i=0;i<n;i++) this.subTrees[i] = new SearchTree();
+        nextAlternative = 0;
+      }
+
+      public void UpdatePath() {
+        System.Diagnostics.Debug.Assert(!Done);
+        if (IsUninitialized) { return; }
+        Count++;
+        if (subTrees.Length == 0) {
+          Done = true;
+        }
+        if (IsAlternativeNode) {
+          // update only the active alternative and calculate a new alternative
+          subTrees[nextAlternative].UpdatePath();
+
+          do {
+            nextAlternative = (nextAlternative + 1) % subTrees.Length;
+          } while (subTrees[nextAlternative] != null && subTrees[nextAlternative].Done);
+
+          // from the nodes which are not done take the first with minimum count
+          //nextAlternative = (from i in Enumerable.Range(0, subTrees.Length)
+          //                   where subTrees[i] == null || !subTrees[i].Done
+          //                   orderby subTrees[i]==null?0:subTrees[i].Count ascending
+          //                   select i).FirstOrDefault(); // possibly there are no children left that can be tried
         } else {
-          // non-terminal -> generate alternatives if necessary
-          var alts = Grammar.GetAlternatives(symb);
-          if (alts.Count() == 1) {
-              var eAlt = new PartiallyProcessedSeq(e.Path, alts.Single().Concat(e.Remaining));
-              queue.Enqueue(eAlt);
-              // Console.WriteLine(""In: "" + eAlt);
-          } else {
-            int i = 0;
-            foreach (var alt in alts) {
-              var eAlt = new PartiallyProcessedSeq(e.Path.Concat(new int[] { i++ }), alt.Concat(e.Remaining));
-              queue.Enqueue(eAlt);
-              // Console.WriteLine(""In: "" + eAlt);
-            }
-          }
-        }
-      }
-    }
-
+          // for sequenceNodes update all sub-trees
+          foreach (var t in subTrees) t.UpdatePath();
+        }
+        // set node to done if all nodes are non-null and done
+        this.Done = true;
+        foreach(var t in subTrees) {
+          if(t == null || !t.Done) 
+            { this.Done = false; break; }
+        }        
+      }
+
+      public bool IsAlternativeNode { get; set; }
+      public bool IsSequenceNode { get; set; }
+      public int Count { get; private set; }
+    }
+
+    private SearchTree tree;
     private void Start() {
-      // generate possible paths through the grammar and evaluate each of them    
+      // start with empty tree
+      tree = new SearchTree();
       var bestF = ?MAXIMIZATION? ? double.NegativeInfinity : double.PositiveInfinity;
       int n = 0;
-      foreach(var path in GeneratePaths()) {
-        var length = path.Count();
-        currentPath = path;
+      var sw = new System.Diagnostics.Stopwatch();
+      sw.Start();
+      while (!tree.Done) {
+
         var f = Calculate();
+        // do one more run through the tree to update the path
+        tree.UpdatePath();
+
         n++;
-        if(IsBetter(f, bestF)) bestF = f;
-        if (n%1000 == 0) Console.WriteLine(""{0}\t{1}\t{2}\t{3}"",n, length, bestF, f);
-      }
-    }
-
-    private IEnumerable<int> currentPath;
+        if (IsBetter(f, bestF)) bestF = f;
+        if (n % 100 == 0) {
+          sw.Stop();
+          Console.WriteLine(""{0}\t{1}\t{2}\t({3:0.00} sols/ms)"", n, bestF, f, 100.0 / sw.ElapsedMilliseconds);
+          sw.Reset();
+          sw.Start();
+        }
+      }
+    }
 
     public double Calculate() {
@@ -188 +166 @@
         solverTemplate
           .Replace("?MAXIMIZATION?", ast.FitnessFunctionNode.Maximization.ToString().ToLowerInvariant())
-          .Replace("?GRAMMARCLASSCODE?", GenerateGrammarClassCode(grammar))
           .Replace("?IDENT?", ast.Name)
           .Replace("?FITNESSFUNCTION?", ast.FitnessFunctionNode.SrcCode)
@@ -195 +172 @@
           .Replace("?ADDITIONALCODE?", ast.ClassCodeNode.SrcCode)
           .Replace("?CONSTRAINTSSOURCE?", GenerateConstraintMethods(ast.Terminals))
-          .Replace("?PATHGENERATORCODE?", GeneratePathGeneratorCode(ast))
           ;
 
@@ -248 +224 @@
     }
 
-
-    private string GenerateGrammarClassCode(IGrammar grammar) {
-      var sb = new StringBuilder();
-      // RootSymbol
-      sb.AppendFormat("public static string RootSymbol {{ get {{ return \"{0}\"; }} }}", grammar.StartSymbol.Name).AppendLine();
-      sb.AppendLine("public static HashSet<string> terminalSymbols = new HashSet<string>() {");
-      sb.AppendFormat("{0}", grammar.TerminalSymbols.Aggregate("", (str, symb) => str + "\"" + symb.Name + "\", "));
-      sb.AppendLine("};");
-      // GetAlternatives
-      sb.AppendFormat("public static IEnumerable<IEnumerable<string>> GetAlternatives(string symbol) {{");
-      sb.AppendFormat("switch(symbol) {{ ").AppendLine();
-      foreach (var ntSymbol in grammar.NonTerminalSymbols) {
-        sb.AppendFormat("case \"{0}\": {{ ", ntSymbol.Name).AppendLine();
-        sb.Append("return new string[][] { ").AppendLine();
-        foreach (var alt in grammar.GetAlternatives(ntSymbol)) {
-          sb.Append("new string[] { ")
-            .Append(alt.Skip(1).Aggregate("\"" + alt.First().Name + "\"", (str, symb) => str + ", \"" + symb.Name + "\""))
-            .AppendLine("},");
-        }
-        sb.Append("};");
-        sb.AppendLine("}");
-      }
-      sb.AppendLine(" default: { throw new InvalidOperationException(\"Unkown symbol: \"+symbol); }");
-      sb.AppendLine("}");
-      sb.AppendLine("}");
-
-      sb.AppendLine("public static bool IsTerminal(string symbol) {");
-      sb.AppendFormat("return terminalSymbols.Contains(symbol);");
-      sb.AppendLine("}");
-      // NumberOfAlternatives
-      sb.AppendLine(
-        "public static int NumberOfAlternatives(string symbol) { return GetAlternatives(symbol).Count(); }");
-      return sb.ToString();
-    }
-
-
     // produces helper methods for the attributes of all terminal nodes
     private string GenerateConstraintMethods(List<SymbolNode> symbols) {
@@ -310 +250 @@
     }
 
-
-    // generates code for a breath-first-search generating all possible paths through the grammar
-    private string GeneratePathGeneratorCode(GPDefNode ast) {
-      var sb = new StringBuilder();
-      foreach (var s in ast.NonTerminals.OfType<NonTerminalNode>()) {
-        sb.Append(GeneratePathGeneratorCode(s));
-      }
-
-      sb.Append(GeneratePathGeneratorCode(ast.Terminals.OfType<TerminalNode>()));
-      return sb.ToString();
-    }
-
-    private string GeneratePathGeneratorCode(NonTerminalNode s) {
-      var sb = new StringBuilder();
-
-      return sb.ToString();
-    }
-
-    // generates a method for the terminal that returns all an IEnumerable of int[] representing each possible combination of values for that terminal
-    private string GeneratePathGeneratorCode(IEnumerable<TerminalNode> terminals) {
-      var sb = new StringBuilder();
-      sb.AppendLine("private IEnumerable<IEnumerable<int>> GeneratePathsFor(string tSymbol) {");
-      sb.AppendLine("switch(tSymbol) {");
-      foreach (var t in terminals) {
-        sb.AppendFormat("case \"{0}\": {{", t.Ident).AppendLine();
-        if (t.FieldDefinitions.Any()) {
-          int i = 0;
-          // open for loop for each field
-          foreach (var f in t.FieldDefinitions) {
-            sb.AppendFormat("for(int i{0}=0; i{0} < GetAllowed{1}_{2}().Length; i{0}++) {{", i++, t.Ident, f.Identifier)
-              .
-              AppendLine();
-          }
-          sb.AppendFormat("yield return new int[] {{ {0} }};",
-                          Enumerable.Range(0, i).Select(ii => "i" + ii + ", ").Aggregate((str, e) => str + e));
-          // close braces
-          while (i-- > 0) {
-            sb.AppendLine("}");
-          }
-          sb.AppendLine("break;");
-        } else {
-          sb.AppendLine("yield return Enumerable.Empty<int>();");
-          sb.AppendLine("break;");
-        }
-        sb.AppendLine("}");
-      }
-      sb.AppendLine("} }");
-      return sb.ToString();
-    }
-
     private string GenerateInterpreterSource(AttributedGrammar grammar) {
       var sb = new StringBuilder();
@@ -378 +268 @@
       // e.g.: ProgramRoot(ref int a0) { ProgramRoot(rootNode , ref a0); }
       sb.AppendFormat("void {0}({1}) {{", grammar.StartSymbol.Name, formalParameter).AppendLine();
-      sb.AppendLine(" var path = currentPath.GetEnumerator();");
-      sb.AppendFormat("{0}(path, {1});", grammar.StartSymbol.Name, actualParameter).AppendLine();
-      sb.AppendLine("if(path.MoveNext()) throw new InvalidOperationException(); // assert that the full path has been processed");
+      sb.AppendFormat("{0}(tree, {1});", grammar.StartSymbol.Name, actualParameter).AppendLine();
       sb.AppendLine("}");
 
@@ -397 +285 @@
       // if the terminal symbol has attributes then we must create values for these attributes
       if (!s.Attributes.Any())
-        sb.AppendFormat("private void {0}(IEnumerator<int> path) {{", s.Name);
+        sb.AppendFormat("private void {0}(SearchTree tree) {{", s.Name);
       else
-        sb.AppendFormat("private void {0}(IEnumerator<int> path, {1}) {{", s.Name, s.GetAttributeString());
-
+        sb.AppendFormat("private void {0}(SearchTree tree, {1}) {{", s.Name, s.GetAttributeString());
+
+      sb.AppendFormat("if (tree.IsUninitialized) {{ tree.SetNumberOfSubtrees({0}); tree.IsSequenceNode = true; }}", s.Attributes.Count());
       // each field must match a formal parameter, assign a value for each parameter
+      int i = 0;
       foreach (var element in s.Attributes) {
         // read next symbol
-        sb.AppendLine("path.MoveNext();");
-        sb.AppendFormat("{0} = Get{1}_{0}Element(path.Current)", element.Name, s.Name).AppendLine(";");
+        sb.AppendLine("throw new NotImplementedException(); // this is not yet supported ");
+        sb.AppendFormat("{0} = Get{1}_{0}Element(tree.GetSubTree({2}).GetAlternative())", element.Name, s.Name, i++).AppendLine(";");
       }
       sb.AppendLine("}");
@@ -414 +304 @@
       var sb = new StringBuilder();
       if (!s.Attributes.Any())
-        sb.AppendFormat("private void {0}(IEnumerator<int> path) {{", s.Name);
+        sb.AppendFormat("private void {0}(SearchTree tree) {{", s.Name);
       else
-        sb.AppendFormat("private void {0}(IEnumerator<int> path, {1}) {{", s.Name, s.GetAttributeString());
+        sb.AppendFormat("private void {0}(SearchTree tree, {1}) {{", s.Name, s.GetAttributeString());
+
       // generate local definitions
       sb.AppendLine(g.GetLocalDefinitions(s));
 
 
-      // if there are alternatives for this symbol -> choose alternative based on the path
-      var alts = g.GetAlternatives(s);
-      if (alts.Count() > 1) {
-        // read next symbol
-        sb.AppendLine("path.MoveNext();");
+
+      // make sure we first descent into terminal alternatives -> we just order by number of non-terminals in the alternative
+      var altsWithSemActions = g.GetAlternativesWithSemanticActions(s).OrderBy(alt => alt.Count(symb => g.IsNonTerminal(symb))).ToArray();
+
+      if (altsWithSemActions.Length > 1) {
+        sb.AppendFormat("      if (tree.IsUninitialized) {{ tree.SetNumberOfSubtrees({0}); tree.IsAlternativeNode = true; }}", altsWithSemActions.Length);
+
         int i = 0;
-        sb.AppendLine("switch(path.Current) {");
+        sb.AppendLine("switch(tree.GetNextAlternative()) {");
         // generate a case for each alternative
-        foreach (var l in alts) {
+        foreach (var alt in altsWithSemActions) {
           sb.AppendFormat("case {0}: {{ ", i).AppendLine();
-          foreach (var altS in g.GetAlternativeWithSemanticActions(s, i++)) {
-            sb.AppendLine(GenerateSourceForAction(altS));
+          sb.AppendLine("SearchTree subtree = null; ");
+
+          // this only works for alternatives with a single non-terminal symbol (ignoring semantic symbols) so far!
+          // handling multiple non-terminals here would require a change in the structure of the search tree
+          // another way to handle this is through grammar transformation (the examplary grammars all have the correct from)
+          Debug.Assert(alt.Count(symb => !(symb is SemanticSymbol)) == 1);
+          foreach (var altSymb in alt) {
+            if (!(altSymb is SemanticSymbol)) sb.AppendFormat("subtree = tree.GetSubtree({0}); ", i);
+            sb.AppendLine(GenerateSourceForAction(altSymb));
           }
+          i++;
           sb.AppendLine("break;").AppendLine("}");
         }
         sb.AppendLine("default: throw new System.InvalidOperationException();").AppendLine("}");
       } else {
-        foreach (var altS in g.GetAlternativeWithSemanticActions(s, 0)) {
-          sb.AppendLine(GenerateSourceForAction(altS));
+        sb.AppendFormat("      if (tree.IsUninitialized) {{ tree.SetNumberOfSubtrees({0}); tree.IsSequenceNode = true; }}", altsWithSemActions.Single().Count(symb => !(symb is SemanticSymbol)));
+        int j = 0;
+        sb.AppendLine("SearchTree subtree = null; ");
+        foreach (var altSymb in altsWithSemActions.Single()) {
+          if (!(altSymb is SemanticSymbol)) sb.AppendFormat("subtree = tree.GetSubtree({0}); ", j++);
+          sb.AppendLine(GenerateSourceForAction(altSymb));
         }
       }
@@ -453 +358 @@
       } else {
         if (!s.Attributes.Any())
-          return string.Format("{0}(path);", s.Name);
+          return string.Format("{0}(subtree);", s.Name);
         else
-          return string.Format("{0}(path, {1});", s.Name, s.GetAttributeString());
+          return string.Format("{0}(subtree, {1});", s.Name, s.GetAttributeString());
       }
     }

branches/HeuristicLab.Problems.GPDL/Examples/Artificial Ant.txt

@@ -86 +86 @@
   
   public void Reset() {
-    world = LosAltosTrail.Select(l=>l.ToArray()).ToArray();
+    for(int row = 0; row<world.Length;row++)
+      for(int col = 0; col < world[row].Length; col++) {
+        world[row][col] = LosAltosTrail[row][col];
+      }
   }
   
@@ -209 +212 @@
   .
 
-  Prog2<<World world, AntState state>> = 
+  Prog2<<World world, AntState state>> =
     Ant<<world, state>> Ant<<world, state>>
   .