Ignore:
Timestamp:
02/23/18 18:10:30 (22 months ago)
Author:
lkammere
Message:

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

Location:
branches/2886_SymRegGrammarEnumeration
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • branches/2886_SymRegGrammarEnumeration

    • Property svn:ignore
      •  

        old new  
        11TestResults
         2*.gitignore
    • Property svn:global-ignores set to
      .git
  • branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs

    r15806 r15812  
    7070    public Dictionary<int, SymbolString> DistinctSentences { get; private set; }  // Semantically distinct sentences in a run.
    7171    public Dictionary<int, List<SymbolString>> AllSentences { get; private set; } // All sentences ever generated in a run.
    72     public Dictionary<int, SymbolString> ArchivedPhrases { get; private set; }    // Nodes in the search tree
     72    public HashSet<int> ArchivedPhrases { get; private set; }
     73
    7374    internal SearchDataStore OpenPhrases { get; private set; }                    // Stack/Queue/etc. for fetching the next node in the search tree. 
    7475
     
    104105
    105106      AllSentences = new Dictionary<int, List<SymbolString>>();
    106       ArchivedPhrases = new Dictionary<int, SymbolString>(); // Nodes in the search tree
     107      ArchivedPhrases = new HashSet<int>();
     108
    107109      DistinctSentences = new Dictionary<int, SymbolString>();
    108110      Expansions = 0;
     
    125127          StoredSymbolString fetchedPhrase = OpenPhrases.GetNext();
    126128          SymbolString currPhrase = fetchedPhrase.SymbolString;
    127 
     129#if DEBUG
    128130          LogSearchGraph(dotFileTrace, $"{fetchedPhrase.Hash} [label=\"{Grammar.PostfixToInfixParser(fetchedPhrase.SymbolString)}\"];");
    129 
    130           ArchivedPhrases.Add(fetchedPhrase.Hash, currPhrase);
     131#endif
     132          ArchivedPhrases.Add(fetchedPhrase.Hash);
    131133
    132134          // expand next nonterminal symbols
     
    135137
    136138          foreach (Production productionAlternative in expandedSymbol.Alternatives) {
    137             SymbolString newPhrase = new SymbolString(currPhrase);
     139            SymbolString newPhrase = new SymbolString(currPhrase.Count + productionAlternative.Count);
     140            newPhrase.AddRange(currPhrase);
    138141            newPhrase.RemoveAt(nonterminalSymbolIndex);     // TODO: removeat and insertRange are both O(n)
    139142            newPhrase.InsertRange(nonterminalSymbolIndex, productionAlternative);
     
    142145            if (newPhrase.Count <= MaxTreeSize) {
    143146              var phraseHash = Grammar.CalcHashCode(newPhrase);
    144 
     147#if DEBUG
    145148              LogSearchGraph(dotFileTrace, $"{fetchedPhrase.Hash} -> {phraseHash} [label=\"{expandedSymbol.StringRepresentation} + &rarr; {productionAlternative}\"];");
    146 
     149#endif
    147150              if (newPhrase.IsSentence()) {
    148151                // Sentence was generated.
     
    155158                  EvaluateSentence(newPhrase);
    156159
     160#if DEBUG
    157161                  LogSearchGraph(dotFileTrace, $"{phraseHash} [label=\"{Grammar.PostfixToInfixParser(newPhrase)}\", style=\"filled\"];");
     162#endif
    158163                }
    159                 UpdateView(AllSentences, DistinctSentences);
    160 
    161               } else if (!OpenPhrases.Contains(phraseHash) && !ArchivedPhrases.ContainsKey(phraseHash)) {
     164                UpdateView();
     165
     166              } else if (!OpenPhrases.Contains(phraseHash) && !ArchivedPhrases.Contains(phraseHash)) {
    162167                OpenPhrases.Store(phraseHash, newPhrase);
    163168              }
     
    165170          }
    166171        }
    167 
     172#if DEBUG
    168173        // Overwrite formatting of start search node and best found solution.
    169174        LogSearchGraph(dotFileTrace, $"{Grammar.CalcHashCode(BestTrainingSentence)} [label=\"{Grammar.PostfixToInfixParser(BestTrainingSentence)}\", shape=Mcircle, style=\"filled,bold\"];");
    170175        LogSearchGraph(dotFileTrace, $"{phrase0Hash} [label=\"{Grammar.PostfixToInfixParser(phrase0)}\", shape=doublecircle];}}");
    171176        dotFileTrace.Flush();
    172       }
    173 
    174       UpdateView(AllSentences, DistinctSentences, force: true);
     177#endif
     178      }
     179
     180      UpdateView(force: true);
    175181      UpdateFinalResults();
    176182    }
     
    184190    }
    185191
    186     #region Evaluation of generated models.
     192#region Evaluation of generated models.
    187193
    188194    // Evaluate sentence within an algorithm run.
     
    208214    }
    209215
    210     #endregion
    211 
    212     #region Visualization in HL
     216#endregion
     217
     218#region Visualization in HL
    213219    // Initialize entries in result set.
    214220    private void InitResults() {
     
    228234    // Update the view for intermediate results in an algorithm run.
    229235    private int updates;
    230     private void UpdateView(Dictionary<int, List<SymbolString>> allGenerated,
    231         Dictionary<int, SymbolString> distinctGenerated, bool force = false) {
     236    private void UpdateView(bool force = false) {
    232237      updates++;
    233238
    234       if (force || updates % GuiUpdateInterval == 0) {
    235         var allGeneratedEnum = allGenerated.Values.SelectMany(x => x).ToArray();
     239      if (force || updates % GuiUpdateInterval == 1) {
     240        var allGeneratedEnum = AllSentences.Values.SelectMany(x => x).ToArray();
    236241        ((IntValue)Results[GeneratedPhrasesName].Value).Value = ArchivedPhrases.Count;
    237242        ((IntValue)Results[SearchStructureSizeName].Value).Value = OpenPhrases.Count;
    238243        ((IntValue)Results[GeneratedSentencesName].Value).Value = allGeneratedEnum.Length;
    239         ((IntValue)Results[DistinctSentencesName].Value).Value = distinctGenerated.Count;
     244        ((IntValue)Results[DistinctSentencesName].Value).Value = DistinctSentences.Count;
    240245        ((IntValue)Results[PhraseExpansionsName].Value).Value = Expansions;
    241246        ((IntValue)Results[GeneratedEqualSentencesName].Value).Value = EqualGeneratedSentences;
     
    279284      Results.Add(new Result("Distinct generated sentences", new StringMatrix(distinctSentencesMatrix)));
    280285    }
    281    
    282     private void LogSearchGraph(TraceListener listener, String msg) {
    283 #if false
     286
     287    private void LogSearchGraph(TraceListener listener, string msg) {
    284288      listener.Write(msg);
    285 #endif
    286     }
    287     #endregion
     289    }
     290#endregion
    288291
    289292  }
Note: See TracChangeset for help on using the changeset viewer.