Changeset 15827


Ignore:
Timestamp:
03/07/18 11:12:28 (3 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:
3 edited

Legend:

Unmodified
Added
Removed
  • branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Grammar.cs

    r15821 r15827  
    214214        for (int i = 0; i < isFactorRemaining.Length; i++) {
    215215          if (!isFactorRemaining[i]) continue;
    216           if (isFactorRemaining.Count() <= 2) break; // Until we have constants, we can't cancel out all terms.
     216          if (isFactorRemaining.Length <= 2) break; // Until we have constants, we can't cancel out all terms.
    217217
    218218          var currFactor = childHashes[i];
     
    224224          }
    225225        }
    226         return Enumerable
    227           .Range(0, isFactorRemaining.Length)
    228           .Where(i => isFactorRemaining[i])
    229           .Select(i => childHashes[i])
     226
     227        return childHashes
     228          .Where((c, i) => isFactorRemaining[i])
    230229          .ToArray();
    231230      }
  • branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs

    r15824 r15827  
    150150
    151151        // expand next nonterminal symbols
    152         int nonterminalSymbolIndex = currPhrase.FindIndex(s => s is NonterminalSymbol);
    153         NonterminalSymbol expandedSymbol = currPhrase[nonterminalSymbolIndex] as NonterminalSymbol;
    154 
    155         foreach (Production productionAlternative in expandedSymbol.Alternatives) {
     152        int nonterminalSymbolIndex = currPhrase.NextNonterminalIndex();
     153        NonterminalSymbol expandedSymbol = (NonterminalSymbol)currPhrase[nonterminalSymbolIndex];
     154        var appliedProductions = expandedSymbol.Alternatives;
     155
     156        for (int i = 0; i < appliedProductions.Count; i++) {
    156157          PhraseExpansionCount++;
    157158
    158           SymbolString newPhrase = new SymbolString(currPhrase.Count + productionAlternative.Count);
    159           newPhrase.AddRange(currPhrase);
    160           newPhrase.RemoveAt(nonterminalSymbolIndex);     // TODO: removeat and insertRange are both O(n)
    161           newPhrase.InsertRange(nonterminalSymbolIndex, productionAlternative);
    162 
    163           if (newPhrase.Count <= MaxTreeSize) {
     159          SymbolString newPhrase = currPhrase.DerivePhrase(nonterminalSymbolIndex, appliedProductions[i]);
     160
     161          if (newPhrase.Count() <= MaxTreeSize) {
    164162            var phraseHash = Grammar.CalcHashCode(newPhrase);
    165163
    166             OnPhraseDerived(fetchedPhrase.Hash, fetchedPhrase.SymbolString, phraseHash, newPhrase, expandedSymbol, productionAlternative);
     164            OnPhraseDerived(fetchedPhrase.Hash, fetchedPhrase.SymbolString, phraseHash, newPhrase, expandedSymbol, appliedProductions[i]);
    167165
    168166            if (newPhrase.IsSentence()) {
    169167              AllGeneratedSentencesCount++;
    170168
    171               OnSentenceGenerated(fetchedPhrase.Hash, fetchedPhrase.SymbolString, phraseHash, newPhrase, expandedSymbol, productionAlternative);
    172 
    173               if (!DistinctSentencesLength.ContainsKey(phraseHash) || DistinctSentencesLength[phraseHash] > newPhrase.Count) {
     169              OnSentenceGenerated(fetchedPhrase.Hash, fetchedPhrase.SymbolString, phraseHash, newPhrase, expandedSymbol, appliedProductions[i]);
     170
     171              if (!DistinctSentencesLength.ContainsKey(phraseHash) || DistinctSentencesLength[phraseHash] > newPhrase.Count()) {
    174172                if (DistinctSentencesLength.ContainsKey(phraseHash)) OverwrittenSentencesCount++; // for analysis only
    175173
    176                 DistinctSentencesLength[phraseHash] = newPhrase.Count;
    177                 OnDistinctSentenceGenerated(fetchedPhrase.Hash, fetchedPhrase.SymbolString, phraseHash, newPhrase, expandedSymbol, productionAlternative);
     174                DistinctSentencesLength[phraseHash] = newPhrase.Count();
     175                OnDistinctSentenceGenerated(fetchedPhrase.Hash, fetchedPhrase.SymbolString, phraseHash, newPhrase, expandedSymbol, appliedProductions[i]);
    178176              }
    179177              UpdateView();
  • branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Sentence.cs

    r15812 r15827  
    11using System;
     2using System.Collections;
    23using System.Collections.Generic;
     4using System.Diagnostics;
    35using System.Linq;
    4 using System.Text;
    5 using System.Threading.Tasks;
    66
    77namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.GrammarEnumeration {
    8   public class SymbolString : List<Symbol> {
     8  public class SymbolString : IEnumerable<Symbol> {
     9    private readonly Symbol[] symbols;
    910
    10     public SymbolString(int capacity) : base(capacity) { }
     11    public Symbol this[int index] {
     12      get { return symbols[index]; }
     13    }
    1114
    12     public SymbolString(IEnumerable<Symbol> symbols) : base(symbols) { }
     15    public SymbolString(IEnumerable<Symbol> s) {
     16      symbols = s.ToArray();
     17    }
     18
     19    public SymbolString(params Symbol[] s) {
     20      symbols = s;
     21    }
    1322
    1423    public bool IsSentence() {
    15       return this.All(sym => sym is TerminalSymbol);
     24      return !this.Any(sym => sym is NonterminalSymbol);
    1625    }
    1726
    1827    public int[] GetNonterminalSymbolIndexes() {
    19       return Enumerable.Range(0, Count)
    20         .Where(i => this[i] is NonterminalSymbol)
     28      return Enumerable.Range(0, symbols.Length)
     29        .Where(i => symbols[i] is NonterminalSymbol)
    2130        .ToArray();
    2231    }
    2332
     33    public int NextNonterminalIndex() {
     34      Debug.Assert(!IsSentence());
     35      int firstNonTerminalIndex = 0;
     36      while (firstNonTerminalIndex < symbols.Length && symbols[firstNonTerminalIndex] is TerminalSymbol) {
     37        firstNonTerminalIndex++;
     38      }
     39      return firstNonTerminalIndex;
     40    }
     41
     42    public SymbolString DerivePhrase(int nonterminalSymbolIndex, Production production) {
     43      int productionLength = production.Count;
     44      int newStringLength = Count() + productionLength - 1;
     45      Symbol[] newPhrase = new Symbol[newStringLength];
     46
     47      // Copy "left" part of the phrase
     48      Array.Copy(symbols, 0, newPhrase, 0, nonterminalSymbolIndex);
     49      // Copy production and overwrite nonterminalsymbol
     50      production.CopyTo(0, newPhrase, nonterminalSymbolIndex, productionLength);
     51      // Copy "right" part of the original phrase
     52      Array.Copy(symbols, nonterminalSymbolIndex + 1, newPhrase, nonterminalSymbolIndex + productionLength, symbols.Length - nonterminalSymbolIndex - 1);
     53
     54      return new SymbolString(newPhrase);
     55    }
     56
    2457    public override string ToString() {
    25       return string.Join(" ", this);
     58      return string.Join<Symbol>(" ", symbols);
    2659    }
     60
     61    #region Enumerable interface
     62    IEnumerator IEnumerable.GetEnumerator() {
     63      return GetEnumerator();
     64    }
     65
     66    public IEnumerator<Symbol> GetEnumerator() {
     67      return ((IEnumerable<Symbol>)symbols).GetEnumerator();
     68    }
     69
     70    public int Count() {
     71      return symbols.Length;
     72    }
     73    #endregion
    2774  }
    2875}
Note: See TracChangeset for help on using the changeset viewer.