Changeset 16176


Ignore:
Timestamp:
09/22/18 21:57:59 (13 months ago)
Author:
bburlacu
Message:

#2886: Fix hashing

Location:
branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration
Files:
2 edited

Legend:

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

    r16053 r16176  
    2626namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration {
    2727  [StorableClass]
    28   public abstract class Symbol : DeepCloneable, IEquatable<Symbol> {
     28  public abstract class Symbol : DeepCloneable, IEquatable<Symbol>, IComparable<Symbol> {
    2929    [Storable]
    3030    private readonly int stringRepresentationHash;
     
    7878      return stringRepresentationHash;
    7979    }
     80
     81    public int CompareTo(Symbol other) {
     82      var v1 = this as VariableTerminalSymbol;
     83      var v2 = other as VariableTerminalSymbol;
     84
     85      if ((v1 == null && v2 == null) || (v1 != null && v2 != null))
     86        return this.StringRepresentation.CompareTo(other.StringRepresentation);
     87      return v1 == null ? 1 : -1;
     88    }
    8089    #endregion
    8190  }
     
    119128    protected NonterminalSymbol(bool deserializing) : base(deserializing) { }
    120129  }
    121 
    122 
    123130}
  • branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Hashing/Hasher.cs

    r16053 r16176  
    2828
    2929namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration {
     30
    3031  [StorableClass]
    3132  public abstract class Hasher<THashType> : DeepCloneable {
     33    protected struct HashItem : IComparable<HashItem>, IEquatable<HashItem> {
     34      public THashType Value { get; private set; }
     35      public Symbol Symbol { get; private set; }
     36
     37      public int CompareTo(HashItem other) {
     38        var res = Symbol.CompareTo(other.Symbol);
     39        return res == 0 ? Comparer<THashType>.Default.Compare(Value, other.Value) : res;
     40      }
     41
     42      private HashItem(THashType h, Symbol s) {
     43        Value = h;
     44        Symbol = s;
     45      }
     46
     47      public static HashItem Create(THashType h, Symbol s) {
     48        return new HashItem(h, s);
     49      }
     50
     51      public bool Equals(HashItem other) {
     52        return Symbol.Equals(other.Symbol) && Value.Equals(other.Value);
     53      }
     54    }
    3255    protected Hasher(Grammar grammar) {
    3356      Grammar = grammar;
     
    4164    protected Grammar Grammar { get; private set; }
    4265
    43     protected abstract THashType AggregateHashes(Symbol operatorSym, IList<THashType> hashes);
     66    protected abstract HashItem AggregateHashes(Symbol operatorSym, IList<HashItem> hashes);
    4467
    4568    public int CalcHashCode(SymbolList sentence) {
     
    4972
    5073      Symbol peek = parseStack.Peek();
    51       return AggregateHashes(peek, GetSubtreeHashes(parseStack)).GetHashCode();
     74      return AggregateHashes(peek, GetSubtreeHashes(parseStack)).Value.GetHashCode();
    5275    }
    5376
     
    5578    protected Hasher(bool deserializing) { }
    5679
    57     private IList<THashType> GetSubtreeHashes(Stack<Symbol> parseStack) {
     80    private IList<HashItem> GetSubtreeHashes(Stack<Symbol> parseStack) {
    5881      Symbol currentSymbol = parseStack.Pop();
    5982
     
    7295          currentSymbol == Grammar.Sin || currentSymbol == Grammar.Inv) {
    7396        // Directly aggregate the single subtree
    74         return new[] { AggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack)) };
     97        return new[] { AggregateHashes(currentSymbol, GetSubtreeHashes(parseStack)) };
    7598      }
    7699
    77100      // var, const or nonterminal symbol
    78       return new[] { AggregateHashes(currentSymbol, new THashType[0]) };
    79     }
    80 
    81     private void AddAdditionChildHashes(HashSet<THashType> hashSet, Stack<Symbol> symbolStack) {
     101      return new[] { AggregateHashes(currentSymbol, new HashItem[0]) };
     102    }
     103
     104    private void AddAdditionChildHashes(HashSet<HashItem> hashSet, Stack<Symbol> symbolStack) {
    82105      var peek = symbolStack.Peek();
    83106      var hashes = GetSubtreeHashes(symbolStack); // will pop the stack
     
    89112    }
    90113
    91     private IList<THashType> GetAdditionSubtreeHashes(Stack<Symbol> parseStack) {
    92       var uniqueChildHashes = new HashSet<THashType>();
     114    private IList<HashItem> GetAdditionSubtreeHashes(Stack<Symbol> parseStack) {
     115      var uniqueChildHashes = new HashSet<HashItem>();
    93116
    94117      AddAdditionChildHashes(uniqueChildHashes, parseStack); // first child
     
    100123    }
    101124
    102     private void AddMultiplicationChildHashes(List<THashType> hashList, Stack<Symbol> symbolStack) {
     125    private void AddMultiplicationChildHashes(List<HashItem> hashList, Stack<Symbol> symbolStack) {
    103126      var peek = symbolStack.Peek();
    104127      var hashes = GetSubtreeHashes(symbolStack);
     
    109132    }
    110133
    111     public IList<THashType> GetMultiplicationSubtreeHashes(Stack<Symbol> parseStack) {
    112       var childHashes = new List<THashType>();
     134    private IList<HashItem> GetMultiplicationSubtreeHashes(Stack<Symbol> parseStack) {
     135      var childHashes = new List<HashItem>();
    113136
    114137      AddMultiplicationChildHashes(childHashes, parseStack); // first child
     
    159182    protected IntHasher(bool deserializing) : base(deserializing) { }
    160183
    161     protected override int AggregateHashes(Symbol operatorSym, IList<int> hashes) {
     184    protected override HashItem AggregateHashes(Symbol operatorSym, IList<HashItem> hashes) {
    162185      int start;
    163186      if ((operatorSym == Grammar.Addition || operatorSym == Grammar.Multiplication) && hashes.Count <= 1) {
     
    165188
    166189      } else if (operatorSym is NonterminalSymbol || operatorSym is VariableTerminalSymbol) {
    167         return operatorSym.StringRepresentation.GetHashCode();
     190        return HashItem.Create(operatorSym.StringRepresentation.GetHashCode(), operatorSym);
    168191
    169192      } else {
     
    172195
    173196      for (int i = 0; i < hashes.Count; i++) {
    174         start = ((start << 5) + start) ^ hashes[i];
    175       }
    176       return start;
     197        start = ((start << 5) + start) ^ hashes[i].Value;
     198      }
     199      return HashItem.Create(start, operatorSym);
    177200    }
    178201  }
     
    191214    protected StringHasher(bool deserializing) : base(deserializing) { }
    192215
    193     protected override string AggregateHashes(Symbol operatorSym, IList<string> hashes) {
     216    protected override HashItem AggregateHashes(Symbol operatorSym, IList<HashItem> hashes) {
    194217      var hashesArray = hashes.ToArray();
    195218
     
    198221      }
    199222      if (operatorSym is NonterminalSymbol || operatorSym is VariableTerminalSymbol) {
    200         return operatorSym.StringRepresentation;
    201       }
    202 
    203       return $"[{operatorSym.StringRepresentation} ° {string.Join(" ° ", hashesArray)}]";
     223        return HashItem.Create(operatorSym.StringRepresentation, operatorSym);
     224      }
     225
     226      return HashItem.Create($"[{operatorSym.StringRepresentation} ° {string.Join(" ° ", hashesArray.Select(x => x.Value))}]", operatorSym);
    204227    }
    205228  }
Note: See TracChangeset for help on using the changeset viewer.