Changeset 15827

Timestamp:

03/07/18 11:12:28 (7 years ago)

Author:

lkammere

Message:

#2886: Change implementation of symbol strings from list to array.

Location:

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

Files:

• Grammar.cs (modified) (2 diffs)
• GrammarEnumerationAlgorithm.cs (modified) (1 diff)
• Sentence.cs (modified) (1 diff)

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

@@ -214 +214 @@
         for (int i = 0; i < isFactorRemaining.Length; i++) {
           if (!isFactorRemaining[i]) continue;
-          if (isFactorRemaining.Count() <= 2) break; // Until we have constants, we can't cancel out all terms.
+          if (isFactorRemaining.Length <= 2) break; // Until we have constants, we can't cancel out all terms.
 
           var currFactor = childHashes[i];
@@ -224 +224 @@
           }
         }
-        return Enumerable
-          .Range(0, isFactorRemaining.Length)
-          .Where(i => isFactorRemaining[i])
-          .Select(i => childHashes[i])
+
+        return childHashes
+          .Where((c, i) => isFactorRemaining[i])
           .ToArray();
       }

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

@@ -150 +150 @@
 
         // expand next nonterminal symbols
-        int nonterminalSymbolIndex = currPhrase.FindIndex(s => s is NonterminalSymbol);
-        NonterminalSymbol expandedSymbol = currPhrase[nonterminalSymbolIndex] as NonterminalSymbol;
-
-        foreach (Production productionAlternative in expandedSymbol.Alternatives) {
+        int nonterminalSymbolIndex = currPhrase.NextNonterminalIndex();
+        NonterminalSymbol expandedSymbol = (NonterminalSymbol)currPhrase[nonterminalSymbolIndex];
+        var appliedProductions = expandedSymbol.Alternatives;
+
+        for (int i = 0; i < appliedProductions.Count; i++) {
           PhraseExpansionCount++;
 
-          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);
-
-          if (newPhrase.Count <= MaxTreeSize) {
+          SymbolString newPhrase = currPhrase.DerivePhrase(nonterminalSymbolIndex, appliedProductions[i]);
+
+          if (newPhrase.Count() <= MaxTreeSize) {
             var phraseHash = Grammar.CalcHashCode(newPhrase);
 
-            OnPhraseDerived(fetchedPhrase.Hash, fetchedPhrase.SymbolString, phraseHash, newPhrase, expandedSymbol, productionAlternative);
+            OnPhraseDerived(fetchedPhrase.Hash, fetchedPhrase.SymbolString, phraseHash, newPhrase, expandedSymbol, appliedProductions[i]);
 
             if (newPhrase.IsSentence()) {
               AllGeneratedSentencesCount++;
 
-              OnSentenceGenerated(fetchedPhrase.Hash, fetchedPhrase.SymbolString, phraseHash, newPhrase, expandedSymbol, productionAlternative);
-
-              if (!DistinctSentencesLength.ContainsKey(phraseHash) || DistinctSentencesLength[phraseHash] > newPhrase.Count) {
+              OnSentenceGenerated(fetchedPhrase.Hash, fetchedPhrase.SymbolString, phraseHash, newPhrase, expandedSymbol, appliedProductions[i]);
+
+              if (!DistinctSentencesLength.ContainsKey(phraseHash) || DistinctSentencesLength[phraseHash] > newPhrase.Count()) {
                 if (DistinctSentencesLength.ContainsKey(phraseHash)) OverwrittenSentencesCount++; // for analysis only
 
-                DistinctSentencesLength[phraseHash] = newPhrase.Count;
-                OnDistinctSentenceGenerated(fetchedPhrase.Hash, fetchedPhrase.SymbolString, phraseHash, newPhrase, expandedSymbol, productionAlternative);
+                DistinctSentencesLength[phraseHash] = newPhrase.Count();
+                OnDistinctSentenceGenerated(fetchedPhrase.Hash, fetchedPhrase.SymbolString, phraseHash, newPhrase, expandedSymbol, appliedProductions[i]);
               }
               UpdateView();

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

@@ -1 +1 @@
 using System;
+using System.Collections;
 using System.Collections.Generic;
+using System.Diagnostics;
 using System.Linq;
-using System.Text;
-using System.Threading.Tasks;
 
 namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.GrammarEnumeration {
-  public class SymbolString : List<Symbol> {
+  public class SymbolString : IEnumerable<Symbol> {
+    private readonly Symbol[] symbols;
 
-    public SymbolString(int capacity) : base(capacity) { }
+    public Symbol this[int index] {
+      get { return symbols[index]; }
+    }
 
-    public SymbolString(IEnumerable<Symbol> symbols) : base(symbols) { }
+    public SymbolString(IEnumerable<Symbol> s) {
+      symbols = s.ToArray();
+    }
+
+    public SymbolString(params Symbol[] s) {
+      symbols = s;
+    }
 
     public bool IsSentence() {
-      return this.All(sym => sym is TerminalSymbol);
+      return !this.Any(sym => sym is NonterminalSymbol);
     }
 
     public int[] GetNonterminalSymbolIndexes() {
-      return Enumerable.Range(0, Count)
-        .Where(i => this[i] is NonterminalSymbol)
+      return Enumerable.Range(0, symbols.Length)
+        .Where(i => symbols[i] is NonterminalSymbol)
         .ToArray();
     }
 
+    public int NextNonterminalIndex() {
+      Debug.Assert(!IsSentence());
+      int firstNonTerminalIndex = 0;
+      while (firstNonTerminalIndex < symbols.Length && symbols[firstNonTerminalIndex] is TerminalSymbol) {
+        firstNonTerminalIndex++;
+      }
+      return firstNonTerminalIndex;
+    }
+
+    public SymbolString DerivePhrase(int nonterminalSymbolIndex, Production production) {
+      int productionLength = production.Count;
+      int newStringLength = Count() + productionLength - 1;
+      Symbol[] newPhrase = new Symbol[newStringLength];
+
+      // Copy "left" part of the phrase
+      Array.Copy(symbols, 0, newPhrase, 0, nonterminalSymbolIndex);
+      // Copy production and overwrite nonterminalsymbol
+      production.CopyTo(0, newPhrase, nonterminalSymbolIndex, productionLength);
+      // Copy "right" part of the original phrase
+      Array.Copy(symbols, nonterminalSymbolIndex + 1, newPhrase, nonterminalSymbolIndex + productionLength, symbols.Length - nonterminalSymbolIndex - 1);
+
+      return new SymbolString(newPhrase);
+    }
+
     public override string ToString() {
-      return string.Join(" ", this);
+      return string.Join<Symbol>(" ", symbols);
     }
+
+    #region Enumerable interface
+    IEnumerator IEnumerable.GetEnumerator() {
+      return GetEnumerator();
+    }
+
+    public IEnumerator<Symbol> GetEnumerator() {
+      return ((IEnumerable<Symbol>)symbols).GetEnumerator();
+    }
+
+    public int Count() {
+      return symbols.Length;
+    }
+    #endregion
   }
 }