Changeset 15800 for branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration

Timestamp:

02/21/18 14:57:27 (7 years ago)

Author:

lkammere

Message:

#2886: Refactor code and fix performance issues.

Location:

branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration

Files:

• Grammar.cs (modified) (5 diffs)
• GrammarEnumerationAlgorithm.cs (modified) (7 diffs)
• SearchDataStructure.cs (modified) (1 diff)
• Symbol.cs (modified) (3 diffs)

branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Grammar.cs

@@ -145 +145 @@
     #region Hashing
     public int CalcHashCode(SymbolString sentence) {
+      return CalcHashCode<int>(sentence, AggregateIntHashes);
+    }
+
+    private int CalcHashCode<THashType>(SymbolString sentence, Func<Symbol, IEnumerable<THashType>, THashType> aggregateFunction) {
       Debug.Assert(sentence.Any(), "Trying to evaluate empty sentence!");
-      // Debug.Assert(sentence.All(s => s is TerminalSymbol), "Trying to evaluate symbol sequence with nonterminalsymbols!");
 
       Stack<Symbol> parseStack = new Stack<Symbol>(sentence);
 
       Symbol peek = parseStack.Peek();
-      string[] subtreeHashes = GetSubtreeHashes(parseStack);
-      return AggregateHashes(peek, subtreeHashes).GetHashCode();
-    }
-
-    private string[] GetSubtreeHashes(Stack<Symbol> parseStack) {
+      return aggregateFunction(peek, GetSubtreeHashes(parseStack, aggregateFunction)).GetHashCode();
+    }
+
+    private THashType[] GetSubtreeHashes<THashType>(Stack<Symbol> parseStack, Func<Symbol, IEnumerable<THashType>, THashType> aggregateHashes) {
       Symbol currentSymbol = parseStack.Pop();
 
       // ADDITION
       if (ReferenceEquals(currentSymbol, Addition)) {
-        var uniqueChildHashes = new HashSet<string>();
+        var uniqueChildHashes = new HashSet<THashType>();
 
         // First subtree
         if (ReferenceEquals(parseStack.Peek(), Addition)) {
-          uniqueChildHashes.UnionWith(GetSubtreeHashes(parseStack));
+          uniqueChildHashes.UnionWith(GetSubtreeHashes(parseStack, aggregateHashes));
         } else {
           var peek = parseStack.Peek();
-          uniqueChildHashes.Add(AggregateHashes(peek, GetSubtreeHashes(parseStack)));
+          uniqueChildHashes.Add(aggregateHashes(peek, GetSubtreeHashes(parseStack, aggregateHashes)));
         }
         // Second subtree
         if (ReferenceEquals(parseStack.Peek(), Addition)) {
-          uniqueChildHashes.UnionWith(GetSubtreeHashes(parseStack));
+          uniqueChildHashes.UnionWith(GetSubtreeHashes(parseStack, aggregateHashes));
         } else {
           var peek = parseStack.Peek();
-          uniqueChildHashes.Add(AggregateHashes(peek, GetSubtreeHashes(parseStack)));
+          uniqueChildHashes.Add(aggregateHashes(peek, GetSubtreeHashes(parseStack, aggregateHashes)));
         }
 
@@ -184 +186 @@
       // MULTIPLICATION
       if (ReferenceEquals(currentSymbol, Multiplication)) {
-        var childHashes = new List<string>();
+        var childHashes = new List<THashType>();
 
         // First subtree
         if (ReferenceEquals(parseStack.Peek(), Multiplication)) {
-          childHashes.AddRange(GetSubtreeHashes(parseStack));
+          childHashes.AddRange(GetSubtreeHashes(parseStack, aggregateHashes));
         } else {
-          childHashes.Add(AggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack)));
+          childHashes.Add(aggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack, aggregateHashes)));
         }
         // Second subtree
         if (ReferenceEquals(parseStack.Peek(), Multiplication)) {
-          childHashes.AddRange(GetSubtreeHashes(parseStack));
+          childHashes.AddRange(GetSubtreeHashes(parseStack, aggregateHashes));
         } else {
-          childHashes.Add(AggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack)));
+          childHashes.Add(aggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack, aggregateHashes)));
         }
 
@@ -210 +212 @@
 
           var currFactor = childHashes[i];
-          var invFactor = AggregateHashes(Inv, currFactor.ToEnumerable());
+          var invFactor = aggregateHashes(Inv, currFactor.ToEnumerable());
 
           int indexOfInv = childHashes.IndexOf(invFactor);
@@ -227 +229 @@
       if (ReferenceEquals(currentSymbol, Log) || ReferenceEquals(currentSymbol, Exp) ||
           ReferenceEquals(currentSymbol, Sin) || ReferenceEquals(currentSymbol, Inv)) {
-        return AggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack)).ToEnumerable().ToArray();
+        return new[] { aggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack, aggregateHashes)) };
       }
 
       // var or nonterminal symbol
-      return currentSymbol.StringRepresentation.ToEnumerable().ToArray();
-    }
-
-    private string AggregateHashes(Symbol operatorSym, IEnumerable<string> hashes) {
+      return new[] { aggregateHashes(currentSymbol, Enumerable.Empty<THashType>()) };
+    }
+
+    private string AggregateStringHashes(Symbol operatorSym, IEnumerable<string> hashes) {
       var hashesArray = hashes.ToArray();
 
@@ -240 +242 @@
         return hashesArray[0];
       }
-      if (Var.VariableTerminalSymbols.Contains(operatorSym)) {
+      if (operatorSym is NonterminalSymbol || Var.VariableTerminalSymbols.Contains(operatorSym)) {
         return operatorSym.StringRepresentation;
       }
 
-      return "[" + hashesArray.Aggregate(operatorSym.StringRepresentation, (result, ti) => result + " ° " + ti) + "]";
+      return $"[{hashesArray.Aggregate(operatorSym.StringRepresentation, (result, ti) => string.Concat(result, " ° ", ti))}]";
+    }
+
+    private int AggregateIntHashes(Symbol operatorSym, IEnumerable<int> hashes) {
+      var hashesArray = hashes.ToArray();
+
+      int start;
+      if ((ReferenceEquals(operatorSym, Addition) || ReferenceEquals(operatorSym, Multiplication)) &&
+          hashesArray.Count() <= 1) {
+        start = 0;
+
+      } else if (operatorSym is NonterminalSymbol || Var.VariableTerminalSymbols.Contains(operatorSym)) {
+        return operatorSym.StringRepresentation.GetHashCode();
+
+      } else {
+        start = operatorSym.StringRepresentation.GetHashCode();
+      }
+
+      return hashesArray.Aggregate(start, (result, ti) => ((result << 5) + result) ^ ti.GetHashCode());
     }
 

branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs

@@ -1 +1 @@
 using System;
 using System.Collections.Generic;
+using System.Diagnostics;
+using System.IO;
 using System.Linq;
-using System.Text;
 using System.Threading;
 using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.GrammarEnumeration;
@@ -65 +66 @@
     #endregion
 
-    public Dictionary<int, SymbolString> DistinctSentences;   // Semantically distinct sentences in a run.
-    public Dictionary<int, List<SymbolString>> AllSentences;  // All sentences ever generated in a run.
-    public Dictionary<int, SymbolString> ArchivedPhrases;     // Nodes in the search tree
-    SearchDataStore OpenPhrases;                              // Stack/Queue/etc. for fetching the next node in the search tree.  
-
-    public int EqualGeneratedSentences; // It is not guaranteed that shorter solutions are found first. 
-                                        // When longer solutions are overwritten with shorter ones, 
-                                        // this counter is increased.
-    public int Expansions;              // Number, how many times a nonterminal symbol is replaced with a production rule.
-    public Grammar Grammar;
-
-    public StringBuilder dotFileBuilder;
+    public Dictionary<int, SymbolString> DistinctSentences { get; private set; }  // Semantically distinct sentences in a run.
+    public Dictionary<int, List<SymbolString>> AllSentences { get; private set; } // All sentences ever generated in a run.
+    public Dictionary<int, SymbolString> ArchivedPhrases { get; private set; }    // Nodes in the search tree
+    internal SearchDataStore OpenPhrases { get; private set; }                    // Stack/Queue/etc. for fetching the next node in the search tree.  
+
+    public int EqualGeneratedSentences { get; private set; } // It is not guaranteed that shorter solutions are found first. 
+                                                             // When longer solutions are overwritten with shorter ones, 
+                                                             // this counter is increased.
+    public int Expansions { get; private set; }              // Number, how many times a nonterminal symbol is replaced with a production rule.
+    public Grammar Grammar { get; private set; }
+
+    private readonly string dotFileName = Environment.GetFolderPath(System.Environment.SpecialFolder.DesktopDirectory) + @"\searchgraph.dot";
 
     #region ctors
@@ -84 +85 @@
 
     public GrammarEnumerationAlgorithm() {
-      var provider = new HeuristicLab.Problems.Instances.DataAnalysis.NguyenInstanceProvider(seed: 1234);
-      var regProblem = provider.LoadData(provider.GetDataDescriptors().Single(x => x.Name.Contains("F9 ")));
-
       Problem = new RegressionProblem() {
-        ProblemData = regProblem
+        ProblemData = new HeuristicLab.Problems.Instances.DataAnalysis.NguyenFunctionNine(seed: 1234).GenerateRegressionData()
       };
 
       Parameters.Add(new ValueParameter<IntValue>(MaxTreeSizeParameterName, "The number of clusters.", new IntValue(6)));
-      Parameters.Add(new ValueParameter<IntValue>(GuiUpdateIntervalParameterName, "Number of generated sentences, until GUI is refreshed.", new IntValue(4000)));
-
+      Parameters.Add(new ValueParameter<IntValue>(GuiUpdateIntervalParameterName, "Number of generated sentences, until GUI is refreshed.", new IntValue(1000)));
       Parameters.Add(new ValueParameter<EnumValue<StorageType>>(SearchDataStructureParameterName, new EnumValue<StorageType>(StorageType.Stack)));
     }
@@ -103 +100 @@
       #region init
       InitResults();
-
-      dotFileBuilder = new StringBuilder();
 
       AllSentences = new Dictionary<int, List<SymbolString>>();
@@ -116 +111 @@
       OpenPhrases = new SearchDataStore(SearchDataStructure); // Select search strategy
       var phrase0 = new SymbolString(new[] { Grammar.StartSymbol });
+      var phrase0Hash = Grammar.CalcHashCode(phrase0);
       #endregion
 
-      OpenPhrases.Store(Grammar.CalcHashCode(phrase0), phrase0);
-
-      while (OpenPhrases.Count > 0) {
-        if (cancellationToken.IsCancellationRequested) break;
-
-        StoredSymbolString fetchedPhrase = OpenPhrases.GetNext();
-        SymbolString currPhrase = fetchedPhrase.SymbolString;
-
-        if (dotFileBuilder.Length == 0) {
-          dotFileBuilder.AppendLine("digraph searchgraph {");
-          dotFileBuilder.AppendLine(fetchedPhrase.Hash + " [label=\"" + Grammar.PostfixToInfixParser(fetchedPhrase.SymbolString) + "\", shape=doublecircle];");
-        } else {
-          dotFileBuilder.AppendLine(fetchedPhrase.Hash + " [label=\"" + Grammar.PostfixToInfixParser(fetchedPhrase.SymbolString) + "\"];");
-        }
-
-        ArchivedPhrases.Add(fetchedPhrase.Hash, currPhrase);
-
-        // expand next nonterminal symbols
-        int nonterminalSymbolIndex = currPhrase.FindIndex(s => s is NonterminalSymbol);
-        NonterminalSymbol expandedSymbol = currPhrase[nonterminalSymbolIndex] as NonterminalSymbol;
-
-        foreach (Production productionAlternative in expandedSymbol.Alternatives) {
-          SymbolString newPhrase = new SymbolString(currPhrase);
-          newPhrase.RemoveAt(nonterminalSymbolIndex);
-          newPhrase.InsertRange(nonterminalSymbolIndex, productionAlternative);
-
-          Expansions++;
-          if (newPhrase.Count <= MaxTreeSize) {
-            var phraseHash = Grammar.CalcHashCode(newPhrase);
-
-            dotFileBuilder.AppendLine(fetchedPhrase.Hash + " -> " + phraseHash + " [label=\"" + expandedSymbol.StringRepresentation + "&rarr;" + productionAlternative + "\"];");
-
-            if (newPhrase.IsSentence()) { // Sentence was generated.
-              SaveToAllSentences(phraseHash, newPhrase);
-
-              if (!DistinctSentences.ContainsKey(phraseHash) || DistinctSentences[phraseHash].Count > newPhrase.Count) {
-                if (DistinctSentences.ContainsKey(phraseHash)) EqualGeneratedSentences++; // for analysis only
-
-                DistinctSentences[phraseHash] = newPhrase;
-                EvaluateSentence(newPhrase);
-
-                dotFileBuilder.AppendLine(phraseHash + " [label=\"" + Grammar.PostfixToInfixParser(newPhrase) + "\", style=\"filled\"];");
+      using (TextWriterTraceListener dotFileTrace = new TextWriterTraceListener(new FileStream(dotFileName, FileMode.Create))) {
+        dotFileTrace.Write("digraph searchgraph {"); 
+
+        OpenPhrases.Store(phrase0Hash, phrase0);
+        while (OpenPhrases.Count > 0) {
+          if (cancellationToken.IsCancellationRequested) break;
+
+          StoredSymbolString fetchedPhrase = OpenPhrases.GetNext();
+          SymbolString currPhrase = fetchedPhrase.SymbolString;
+
+          dotFileTrace.Write(
+            $"{fetchedPhrase.Hash} [label=\"{Grammar.PostfixToInfixParser(fetchedPhrase.SymbolString)}\"];");
+
+          ArchivedPhrases.Add(fetchedPhrase.Hash, currPhrase);
+
+          // expand next nonterminal symbols
+          int nonterminalSymbolIndex = currPhrase.FindIndex(s => s is NonterminalSymbol);
+          NonterminalSymbol expandedSymbol = currPhrase[nonterminalSymbolIndex] as NonterminalSymbol;
+
+          foreach (Production productionAlternative in expandedSymbol.Alternatives) {
+            SymbolString newPhrase = new SymbolString(currPhrase);
+            newPhrase.RemoveAt(nonterminalSymbolIndex);
+            newPhrase.InsertRange(nonterminalSymbolIndex, productionAlternative);
+
+            Expansions++;
+            if (newPhrase.Count <= MaxTreeSize) {
+              var phraseHash = Grammar.CalcHashCode(newPhrase);
+
+              dotFileTrace.Write(
+                $"{fetchedPhrase.Hash} -> {phraseHash} [label=\"{expandedSymbol.StringRepresentation} + &rarr; {productionAlternative}\"];");
+
+              if (newPhrase.IsSentence()) {
+                // Sentence was generated.
+                SaveToAllSentences(phraseHash, newPhrase);
+
+                if (!DistinctSentences.ContainsKey(phraseHash) || DistinctSentences[phraseHash].Count > newPhrase.Count) {
+                  if (DistinctSentences.ContainsKey(phraseHash)) EqualGeneratedSentences++; // for analysis only
+
+                  DistinctSentences[phraseHash] = newPhrase;
+                  EvaluateSentence(newPhrase);
+
+                  dotFileTrace.Write(
+                    $"{phraseHash} [label=\"{Grammar.PostfixToInfixParser(newPhrase)}\", style=\"filled\"];");
+                }
+                UpdateView(AllSentences, DistinctSentences);
+
+              } else if (!OpenPhrases.Contains(phraseHash) && !ArchivedPhrases.ContainsKey(phraseHash)) {
+                OpenPhrases.Store(phraseHash, newPhrase);
               }
-              UpdateView(AllSentences, DistinctSentences, Expansions);
-
-            } else if (!OpenPhrases.Contains(phraseHash) && !ArchivedPhrases.ContainsKey(phraseHash)) {
-              OpenPhrases.Store(phraseHash, newPhrase);
             }
           }
         }
-      }
-
-      dotFileBuilder.AppendLine(Grammar.CalcHashCode(BestTrainingSentence) + " [label=\"" + Grammar.PostfixToInfixParser(BestTrainingSentence) + "\", shape=Mcircle, style=\"filled,bold\"];");
-      dotFileBuilder.AppendLine("}");
-
-      System.IO.File.WriteAllText(Environment.GetFolderPath(System.Environment.SpecialFolder.DesktopDirectory)+ @"\searchgraph.dot", dotFileBuilder.ToString());
-
-      UpdateView(AllSentences, DistinctSentences, Expansions, force: true);
+
+        // Overwrite formatting of start search node and best found solution.
+        dotFileTrace.Write(
+          $"{Grammar.CalcHashCode(BestTrainingSentence)} [label=\"{Grammar.PostfixToInfixParser(BestTrainingSentence)}\", shape=Mcircle, style=\"filled,bold\"];");
+        dotFileTrace.Write($"{phrase0Hash} [label=\"{Grammar.PostfixToInfixParser(phrase0)}\", shape=doublecircle];}}");
+        dotFileTrace.Flush();
+      }
+
+      UpdateView(AllSentences, DistinctSentences, force: true);
       UpdateFinalResults();
     }
@@ -230 +229 @@
     private int updates;
     private void UpdateView(Dictionary<int, List<SymbolString>> allGenerated,
-        Dictionary<int, SymbolString> distinctGenerated, int expansions, bool force = false) {
+        Dictionary<int, SymbolString> distinctGenerated, bool force = false) {
       updates++;
 
@@ -237 +236 @@
         ((IntValue)Results[GeneratedSentencesName].Value).Value = allGeneratedEnum.Length;
         ((IntValue)Results[DistinctSentencesName].Value).Value = distinctGenerated.Count;
-        ((IntValue)Results[PhraseExpansionsName].Value).Value = expansions;
+        ((IntValue)Results[PhraseExpansionsName].Value).Value = Expansions;
         ((IntValue)Results[GeneratedEqualSentencesName].Value).Value = EqualGeneratedSentences;
         ((DoubleValue)Results[AverageTreeLengthName].Value).Value = allGeneratedEnum.Select(sentence => sentence.Count).Average();

branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/SearchDataStructure.cs

@@ -6 +6 @@
 
   public struct StoredSymbolString {
-    public int Hash { get; }
-    public SymbolString SymbolString { get; }
+    public readonly int Hash;
+    public readonly SymbolString SymbolString;
 
     public StoredSymbolString(int hash, SymbolString symbolString) {

branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Symbol.cs

@@ -1 +1 @@
 using System.Collections.Generic;
-using System.Linq;
-using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.GrammarEnumeration;
 
 namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration {
 
   public abstract class Symbol {
-    public readonly string StringRepresentation;
+    public string StringRepresentation { get; }
 
     protected Symbol(string representation) {
@@ -22 +20 @@
 
   public class NonterminalSymbol : Symbol {
-    public List<Production> Alternatives;
+    public List<Production> Alternatives { get; }
 
     public NonterminalSymbol(string representation) : base(representation) {
@@ -34 +32 @@
 
   public class VariableSymbol : NonterminalSymbol { // Convenience class
-    public IEnumerable<TerminalSymbol> VariableTerminalSymbols;
+    public IEnumerable<TerminalSymbol> VariableTerminalSymbols { get; }
 
     public VariableSymbol(string representation, IEnumerable<string> variableNames) : base(representation) {