# source:branches/HeuristicLab.Problems.GPDL/CodeGenerator/BruteForceCodeGen.cs@10335

Last change on this file since 10335 was 10335, checked in by gkronber, 7 years ago

#2026 worked on code generator for random search (work in progress commit)

File size: 11.4 KB
Line
1using System;
2using System.Collections.Generic;
3using System.Diagnostics;
4using System.Linq;
5using HeuristicLab.Grammars;
6
7namespace CodeGenerator {
8  public class BruteForceCodeGen {
9    private string solverTemplate = @"
10namespace ?PROBLEMNAME? {
11  public sealed class ?IDENT?Solver {
12
13    private static Dictionary<int, int[]> transition = new Dictionary<int, int[]>() {
14?TRANSITIONTABLE?
15    };
16    private static Dictionary<int, int> subtreeCount = new Dictionary<int, int>() {
17       { -1, 0 }, // terminals
18?SUBTREECOUNTTABLE?
19    };
20
21    private static string[] symb = new string[] { ?SYMBOLNAMES? };
22    private static bool[] isTerminal = new bool[] { ?TERMINALTABLE? };
23    private static bool[] hasAlternatives = new bool[] {?HASALTERNATIVESTABLE? };
24
25
26    public sealed class SolverState : ISolverState {
27      private class Node {
28        public int state;
29        public int count;
30        public List<Node> nodes;
31        public bool done;
32        private int nextAlt;
33        public Node(int state) {
34          this.state = state;
35          nodes = new List<Node>(transition[state].Length);
36          if (!hasAlternatives[state]) {
37            foreach (var t in transition[state]) { nodes.Add(new Node(t)); }
38          }
39        }
40
41        public int GetNextAlternative() {
42          System.Diagnostics.Debug.Assert(hasAlternatives[state]);
43          if(nodes.Count == 0 && !isTerminal[state]) {
44            foreach(var targetState in transition[state]) nodes.Add(new Node(targetState));
45            nextAlt = 0;
46            // begin with a terminal if possible
47            if(!isTerminal[nodes[nextAlt].state])
48              do { nextAlt = (nextAlt + 1) % nodes.Count; } while(nextAlt != 0 /* full circle*/ && !isTerminal[nodes[nextAlt].state]);
49          }
50
51          throw new NotImplementedException(); // TODO: handle terminal classes correctly
52          return nextAlt;
53        }
54
55        public void Update() {
56          count++;
57          if(hasAlternatives[state] && !isTerminal[state]) {
58            nodes[GetNextAlternative()].Update();
59            // check if all nodes done and set this node to done
60            if(nodes.All(n=>n.done)) {
61              this.done = true;
62            } else {
63              // must not walk nodes that are done
64              do { nextAlt = (nextAlt + 1) % nodes.Count; } while (nodes[nextAlt].done);
65            }
66          } else {
67            if(isTerminal[state]) {
68              throw new NotImplementedException(); // TODO: handle terminal classes correctly
69              done = (nextAlt + 1) >= GetAlternativesCount(symb[state]);
70            } else {
71              // update the smallest count. this basically means keeping all sub-trees the same and only altering the updated one
72              Node minNode = nodes.First();
73              foreach(var node in nodes.Skip(1)) {
74                if(node.count < minNode.count) {
75                  minNode = node;
76                }
77              }
78              minNode.Update();
79              if(nodes.All(n=>n.done)) this.done = true;
80            }
81          }
82        }
83      }
84
85
86      ?ALTERNATIVESCOUNTMETHOD?
87
88
89      public int curDepth;
90      public int steps;
91      public int depth;
95
96      public SolverState(IGpdlProblem problem) {
97        this.problem = problem;
98        nodes = new Stack<Node>();
99        searchTree = new Node(0);
100        nodes.Push(searchTree);
101      }
102
103      public void Reset() {
104        System.Diagnostics.Debug.Assert(nodes.Count == 1);
105        steps = 0;
106        depth = 0;
107        curDepth = 0;
108      }
109
110      public int PeekNextAlternative() {
111        var curNode = nodes.Peek();
112        System.Diagnostics.Debug.Assert(hasAlternatives[curNode.state]);
113        return curNode.GetNextAlternative();
114      }
115
116      public void Follow(int idx) {
117        steps++;
118        curDepth++;
119        depth = Math.Max(depth, curDepth);
120        var curNode = nodes.Peek();
121        if(hasAlternatives[curNode.state]) {
122          nodes.Push(curNode.nodes[curNode.GetNextAlternative()]);
123        } else {
124          nodes.Push(curNode.nodes[idx]);
125        }
126      }
127
128      public void Unwind() {
129        nodes.Pop();
130        curDepth--;
131      }
132
133      public void Update() {
134        searchTree.Update();
135      }
136    }
137
138    public static void Main(string[] args) {
139      var problem = new ?IDENT?Problem();
140      var solver = new ?IDENT?Solver(problem);
141      solver.Start();
142    }
143
145    public ?IDENT?Solver(?IDENT?Problem problem) {
146      this.problem = problem;
147    }
148
149    private void Start() {
150      var bestF = ?MAXIMIZATION? ? double.NegativeInfinity : double.PositiveInfinity;
151      int n = 0;
152      long sumDepth = 0;
153      long sumSize = 0;
154      var sumF = 0.0;
155      var sw = new System.Diagnostics.Stopwatch();
156      sw.Start();
157      var _state = new SolverState(problem);
158      while (true) {
159
160        var f = problem.Evaluate(_state);
161        _state.Update();
162
163        n++;
164        sumSize += _state.steps;
165        sumDepth += _state.depth;
166        sumF += f;
167        if (IsBetter(f, bestF)) {
168          // evaluate again with tracing to console
169          // problem.Evaluate(new SolverState(_state.seed, true));
170          bestF = f;
171          Console.WriteLine(""{0}\t{1}\t(size={2}, depth={3})"", n, bestF, _state.steps, _state.depth);
172        }
173        if (n % 1000 == 0) {
174          sw.Stop();
175          Console.WriteLine(""{0}\tbest: {1:0.000}\t(avg: {2:0.000})\t(avg size: {3:0.0})\t(avg. depth: {4:0.0})\t({5:0.00} sols/ms)"", n, bestF, sumF/1000.0, sumSize/1000.0, sumDepth/1000.0, 1000.0 / sw.ElapsedMilliseconds);
176          sw.Reset();
177          sumSize = 0;
178          sumDepth = 0;
179          sumF = 0.0;
180          sw.Start();
181        }
182      }
183    }
184
185    private bool IsBetter(double a, double b) {
186      return ?MAXIMIZATION? ? a > b : a < b;
187    }
188  }
189}";
190
191
192    public void Generate(IGrammar grammar, bool maximization, SourceBuilder problemSourceCode) {
193      var solverSourceCode = new SourceBuilder();
194      solverSourceCode.Append(solverTemplate)
195        .Replace("?MAXIMIZATION?", maximization.ToString().ToLowerInvariant())
196        .Replace("?SYMBOLNAMES?", grammar.Symbols.Select(s => s.Name).Aggregate(string.Empty, (str, symb) => str + "\"" + symb + "\", "))
197        .Replace("?TERMINALTABLE?", grammar.Symbols.Select(grammar.IsTerminal).Aggregate(string.Empty, (str, b) => str + b.ToString().ToLowerInvariant() + ", "))
198        .Replace("?HASALTERNATIVESTABLE?", grammar.Symbols.Select(s => grammar.IsNonTerminal(s) && (grammar.NumberOfAlternatives(s) > 1)).Aggregate(string.Empty, (str, b) => str + b.ToString().ToLowerInvariant() + ", "))
199        .Replace("?TRANSITIONTABLE?", GenerateTransitionTable(grammar))
200        .Replace("?SUBTREECOUNTTABLE?", GenerateSubtreeCountTable(grammar))
201        .Replace("?ALTERNATIVESCOUNTMETHOD?", GenerateAlternativesCountMethod(grammar))
202      ;
203
204      problemSourceCode.Append(solverSourceCode.ToString());
205    }
206
207    #region same as random search
208    private string GenerateTransitionTable(IGrammar grammar) {
209      Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
210      var sb = new SourceBuilder();
211
212      // state idx = idx of the corresponding symbol in the grammar
213      var allSymbols = grammar.Symbols.ToList();
214      var attributes = new List<string>();
215      foreach (var s in grammar.Symbols) {
216        var targetStates = new List<int>();
217        if (grammar.IsTerminal(s)) {
218          foreach (var att in s.Attributes) {
220            attributes.Add(s.Name + "_" + att);
221          }
222        } else {
223          if (grammar.NumberOfAlternatives(s) > 1) {
224            foreach (var alt in grammar.GetAlternatives(s)) {
225              // only single-symbol alternatives are supported
226              Debug.Assert(alt.Count() == 1);
228            }
229          } else {
230            // rule is a sequence of symbols
231            var seq = grammar.GetAlternatives(s).Single();
233          }
234        }
235
236        var targetStateString = targetStates.Aggregate(string.Empty, (str, state) => str + state + ", ");
237
238        var idxOfSourceState = allSymbols.IndexOf(s);
239        sb.AppendFormat("// {0}", s).AppendLine();
240        sb.AppendFormat("{{ {0} , new int[] {{ {1} }} }},", idxOfSourceState, targetStateString).AppendLine();
241      }
242      for (int attIdx = 0; attIdx < attributes.Count; attIdx++) {
243        sb.AppendFormat("// {0}", attributes[attIdx]).AppendLine();
244        sb.AppendFormat("{{ {0} , new int[] {{ }} }},", attIdx + allSymbols.Count).AppendLine();
245      }
246      return sb.ToString();
247    }
248    private string GenerateSubtreeCountTable(IGrammar grammar) {
249      Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
250      var sb = new SourceBuilder();
251
252      // state idx = idx of the corresponding symbol in the grammar
253      var allSymbols = grammar.Symbols.ToList();
254      var attributes = new List<string>();
255      foreach (var s in grammar.Symbols) {
256        int subtreeCount;
257        if (grammar.IsTerminal(s)) {
258          subtreeCount = s.Attributes.Count();
259          attributes.AddRange(s.Attributes.Select(att => s.Name + "_" + att.Name));
260        } else {
261          if (grammar.NumberOfAlternatives(s) > 1) {
262            Debug.Assert(grammar.GetAlternatives(s).All(alt => alt.Count() == 1));
263            subtreeCount = 1;
264          } else {
265            subtreeCount = grammar.GetAlternative(s, 0).Count();
266          }
267        }
268
269        sb.AppendFormat("// {0}", s).AppendLine();
270        sb.AppendFormat("{{ {0} , {1} }},", allSymbols.IndexOf(s), subtreeCount).AppendLine();
271      }
272
273      for (int attIdx = 0; attIdx < attributes.Count; attIdx++) {
274        sb.AppendFormat("// {0}", attributes[attIdx]).AppendLine();
275        sb.AppendFormat("{{ {0} , 1 }},", attIdx + allSymbols.Count).AppendLine();
276      }
277      return sb.ToString();
278    }
279    #endregion
280    private string GenerateAlternativesCountMethod(IGrammar grammar) {
281      Debug.Assert(grammar.Symbols.First().Equals(grammar.StartSymbol));
282      var sb = new SourceBuilder();
283      sb.Append("public int GetAlternativesCount(string symbol, string attribute = null) {").BeginBlock();
284      sb.AppendLine("switch(symbol) {");
285      foreach (var s in grammar.Symbols) {
286        sb.AppendFormat("case \"{0}\":", s.Name).AppendLine();
287        int altCount;
288        if (grammar.IsTerminal(s)) {
289          if (s.Attributes.Any()) {
290            sb.Append("switch(attribute) {").BeginBlock();
291            foreach (var att in s.Attributes) {
292              sb.AppendFormat("case \"{1}\": return problem.GetCardinality(\"{0}\", \"{1}\");", s.Name, att.Name).AppendLine();
293            }
294            sb.Append("} // switch").EndBlock();
295          } else {
296            sb.AppendLine("return 0;");
297          }
298        } else {
299          sb.AppendFormat("return {0};", grammar.NumberOfAlternatives(s)).AppendLine();
300        }
301
302
303      }
304      sb.AppendLine("} // switch");
305      sb.Append("}").EndBlock();
306      return sb.ToString();
307    }
308  }
309}
Note: See TracBrowser for help on using the repository browser.