Changeset 15812

Timestamp:

02/23/18 18:10:30 (7 years ago)

Author:

lkammere

Message:

#2886: Performance Improvements - Only store hash of archived phrases and reduce number of enumerators.

Location:

branches/2886_SymRegGrammarEnumeration

Files:

• . (modified) (2 props)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Grammar.cs (modified) (9 diffs)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs (modified) (11 diffs)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Sentence.cs (modified) (1 diff)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Symbol.cs (modified) (2 diffs)

branches/2886_SymRegGrammarEnumeration

@@ -1 +1 @@
 TestResults
+*.gitignore

@@ -1 +1 @@
 TestResults
+*.gitignore

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

@@ -143 +143 @@
     }
 
-    private int CalcHashCode<THashType>(SymbolString sentence, Func<Symbol, IEnumerable<THashType>, THashType> aggregateFunction) {
+    private int CalcHashCode<THashType>(SymbolString sentence, Func<Symbol, THashType[], THashType> aggregateFunction) {
       Debug.Assert(sentence.Any(), "Trying to evaluate empty sentence!");
 
@@ -152 +152 @@
     }
 
-    private THashType[] GetSubtreeHashes<THashType>(Stack<Symbol> parseStack, Func<Symbol, IEnumerable<THashType>, THashType> aggregateHashes) {
+    private THashType[] GetSubtreeHashes<THashType>(Stack<Symbol> parseStack, Func<Symbol, THashType[], THashType> aggregateHashes) {
       Symbol currentSymbol = parseStack.Pop();
 
@@ -207 +207 @@
 
           var currFactor = childHashes[i];
-          var invFactor = aggregateHashes(Inv, currFactor.ToEnumerable());
+          var invFactor = aggregateHashes(Inv, new[] { currFactor });
 
           int indexOfInv = childHashes.IndexOf(invFactor);
@@ -228 +228 @@
 
       // var or nonterminal symbol
-      return new[] { aggregateHashes(currentSymbol, Enumerable.Empty<THashType>()) };
-    }
-
-    private string AggregateStringHashes(Symbol operatorSym, IEnumerable<string> hashes) {
+      return new[] { aggregateHashes(currentSymbol, new THashType[0]) };
+    }
+
+    private string AggregateStringHashes(Symbol operatorSym, string[] hashes) {
       var hashesArray = hashes.ToArray();
 
@@ -237 +237 @@
         return hashesArray[0];
       }
-      if (operatorSym is NonterminalSymbol || Var.VariableTerminalSymbols.Contains(operatorSym)) {
+      if (operatorSym is NonterminalSymbol || ((TerminalSymbol)operatorSym).IsVariable) {
         return operatorSym.StringRepresentation;
       }
@@ -244 +244 @@
     }
 
-    private int AggregateIntHashes(Symbol operatorSym, IEnumerable<int> hashes) {
-      var hashesArray = hashes.ToArray();
-
+    private int AggregateIntHashes(Symbol operatorSym, int[] hashes) {
       int start;
       if ((ReferenceEquals(operatorSym, Addition) || ReferenceEquals(operatorSym, Multiplication)) &&
-          hashesArray.Count() <= 1) {
+          hashes.Length <= 1) {
         start = 0;
 
-      } else if (operatorSym is NonterminalSymbol || Var.VariableTerminalSymbols.Contains(operatorSym)) {
+      } else if (operatorSym is NonterminalSymbol || ((TerminalSymbol)operatorSym).IsVariable) {
         return operatorSym.StringRepresentation.GetHashCode();
 
@@ -259 +257 @@
       }
 
-      return hashesArray.Aggregate(start, (result, ti) => ((result << 5) + result) ^ ti.GetHashCode());
+      for (int i = 0; i < hashes.Length; i++) {
+        start = ((start << 5) + start) ^ hashes[i];
+      }
+      return start;
     }
     #endregion
@@ -314 +315 @@
         parsedSubTree.AddSubtree(ParseSymbolicExpressionTree(parseStack));
 
-      } else if (Var.VariableTerminalSymbols.Contains(currentSymbol)) {
+      } else if (currentSymbol.IsVariable) {
         VariableTreeNode varNode = (VariableTreeNode)varSy.CreateTreeNode();
         varNode.Weight = 1.0;
@@ -337 +338 @@
       Symbol head = parseStack.Pop();
 
-      SymbolString result = new SymbolString();
+      SymbolString result = new SymbolString(parseStack.Count);
 
       if (ReferenceEquals(head, Addition) || ReferenceEquals(head, Multiplication)) {

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

@@ -70 +70 @@
     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
+    public HashSet<int> ArchivedPhrases { get; private set; }
+
     internal SearchDataStore OpenPhrases { get; private set; }                    // Stack/Queue/etc. for fetching the next node in the search tree.  
 
@@ -104 +105 @@
 
       AllSentences = new Dictionary<int, List<SymbolString>>();
-      ArchivedPhrases = new Dictionary<int, SymbolString>(); // Nodes in the search tree
+      ArchivedPhrases = new HashSet<int>();
+
       DistinctSentences = new Dictionary<int, SymbolString>();
       Expansions = 0;
@@ -125 +127 @@
           StoredSymbolString fetchedPhrase = OpenPhrases.GetNext();
           SymbolString currPhrase = fetchedPhrase.SymbolString;
-
+#if DEBUG
           LogSearchGraph(dotFileTrace, $"{fetchedPhrase.Hash} [label=\"{Grammar.PostfixToInfixParser(fetchedPhrase.SymbolString)}\"];");
-
-          ArchivedPhrases.Add(fetchedPhrase.Hash, currPhrase);
+#endif
+          ArchivedPhrases.Add(fetchedPhrase.Hash);
 
           // expand next nonterminal symbols
@@ -135 +137 @@
 
           foreach (Production productionAlternative in expandedSymbol.Alternatives) {
-            SymbolString newPhrase = new SymbolString(currPhrase);
+            SymbolString newPhrase = new SymbolString(currPhrase.Count + productionAlternative.Count);
+            newPhrase.AddRange(currPhrase);
             newPhrase.RemoveAt(nonterminalSymbolIndex);     // TODO: removeat and insertRange are both O(n)
             newPhrase.InsertRange(nonterminalSymbolIndex, productionAlternative);
@@ -142 +145 @@
             if (newPhrase.Count <= MaxTreeSize) {
               var phraseHash = Grammar.CalcHashCode(newPhrase);
-
+#if DEBUG
               LogSearchGraph(dotFileTrace, $"{fetchedPhrase.Hash} -> {phraseHash} [label=\"{expandedSymbol.StringRepresentation} + &rarr; {productionAlternative}\"];");
-
+#endif
               if (newPhrase.IsSentence()) {
                 // Sentence was generated.
@@ -155 +158 @@
                   EvaluateSentence(newPhrase);
 
+#if DEBUG
                   LogSearchGraph(dotFileTrace, $"{phraseHash} [label=\"{Grammar.PostfixToInfixParser(newPhrase)}\", style=\"filled\"];");
+#endif
                 }
-                UpdateView(AllSentences, DistinctSentences);
-
-              } else if (!OpenPhrases.Contains(phraseHash) && !ArchivedPhrases.ContainsKey(phraseHash)) {
+                UpdateView();
+
+              } else if (!OpenPhrases.Contains(phraseHash) && !ArchivedPhrases.Contains(phraseHash)) {
                 OpenPhrases.Store(phraseHash, newPhrase);
               }
@@ -165 +170 @@
           }
         }
-
+#if DEBUG
         // Overwrite formatting of start search node and best found solution.
         LogSearchGraph(dotFileTrace, $"{Grammar.CalcHashCode(BestTrainingSentence)} [label=\"{Grammar.PostfixToInfixParser(BestTrainingSentence)}\", shape=Mcircle, style=\"filled,bold\"];");
         LogSearchGraph(dotFileTrace, $"{phrase0Hash} [label=\"{Grammar.PostfixToInfixParser(phrase0)}\", shape=doublecircle];}}");
         dotFileTrace.Flush();
-      }
-
-      UpdateView(AllSentences, DistinctSentences, force: true);
+#endif
+      }
+
+      UpdateView(force: true);
       UpdateFinalResults();
     }
@@ -184 +190 @@
     }
 
-    #region Evaluation of generated models.
+#region Evaluation of generated models.
 
     // Evaluate sentence within an algorithm run.
@@ -208 +214 @@
     }
 
-    #endregion
-
-    #region Visualization in HL
+#endregion
+
+#region Visualization in HL
     // Initialize entries in result set.
     private void InitResults() {
@@ -228 +234 @@
     // Update the view for intermediate results in an algorithm run.
     private int updates;
-    private void UpdateView(Dictionary<int, List<SymbolString>> allGenerated,
-        Dictionary<int, SymbolString> distinctGenerated, bool force = false) {
+    private void UpdateView(bool force = false) {
       updates++;
 
-      if (force || updates % GuiUpdateInterval == 0) {
-        var allGeneratedEnum = allGenerated.Values.SelectMany(x => x).ToArray();
+      if (force || updates % GuiUpdateInterval == 1) {
+        var allGeneratedEnum = AllSentences.Values.SelectMany(x => x).ToArray();
         ((IntValue)Results[GeneratedPhrasesName].Value).Value = ArchivedPhrases.Count;
         ((IntValue)Results[SearchStructureSizeName].Value).Value = OpenPhrases.Count;
         ((IntValue)Results[GeneratedSentencesName].Value).Value = allGeneratedEnum.Length;
-        ((IntValue)Results[DistinctSentencesName].Value).Value = distinctGenerated.Count;
+        ((IntValue)Results[DistinctSentencesName].Value).Value = DistinctSentences.Count;
         ((IntValue)Results[PhraseExpansionsName].Value).Value = Expansions;
         ((IntValue)Results[GeneratedEqualSentencesName].Value).Value = EqualGeneratedSentences;
@@ -279 +284 @@
       Results.Add(new Result("Distinct generated sentences", new StringMatrix(distinctSentencesMatrix)));
     }
-   
-    private void LogSearchGraph(TraceListener listener, String msg) {
-#if false
+
+    private void LogSearchGraph(TraceListener listener, string msg) {
       listener.Write(msg);
-#endif
-    }
-    #endregion
+    }
+#endregion
 
   }

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

@@ -8 +8 @@
   public class SymbolString : List<Symbol> {
 
-    public SymbolString() { }
+    public SymbolString(int capacity) : base(capacity) { }
 
     public SymbolString(IEnumerable<Symbol> symbols) : base(symbols) { }

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

@@ -16 +16 @@
 
   public class TerminalSymbol : Symbol {
-    public TerminalSymbol(string representation) : base(representation) { }
+    public readonly bool IsVariable;
+
+    public TerminalSymbol(string representation, bool isVariable = false) : base(representation) {
+      IsVariable = isVariable;
+    }
   }
 
@@ -39 +43 @@
 
       foreach (string variableName in variableNames) {
-        TerminalSymbol s = new TerminalSymbol(variableName);
+        TerminalSymbol s = new TerminalSymbol(variableName, isVariable: true);
         createdSymbols.Add(s);
         AddProduction(s);

@@ -1 +1 @@
 TestResults
+*.gitignore