Changeset 16176 for branches

Timestamp:

09/22/18 21:57:59 (6 years ago)

Author:

bburlacu

Message:

#2886: Fix hashing

Location:

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

Files:

• GrammarEnumeration/Symbol.cs (modified) (3 diffs)
• Hashing/Hasher.cs (modified) (13 diffs)

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

@@ -26 +26 @@
 namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration {
   [StorableClass]
-  public abstract class Symbol : DeepCloneable, IEquatable<Symbol> {
+  public abstract class Symbol : DeepCloneable, IEquatable<Symbol>, IComparable<Symbol> {
     [Storable]
     private readonly int stringRepresentationHash;
@@ -78 +78 @@
       return stringRepresentationHash;
     }
+
+    public int CompareTo(Symbol other) {
+      var v1 = this as VariableTerminalSymbol;
+      var v2 = other as VariableTerminalSymbol;
+
+      if ((v1 == null && v2 == null) || (v1 != null && v2 != null))
+        return this.StringRepresentation.CompareTo(other.StringRepresentation);
+      return v1 == null ? 1 : -1;
+    }
     #endregion
   }
@@ -119 +128 @@
     protected NonterminalSymbol(bool deserializing) : base(deserializing) { }
   }
-
-
 }

branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Hashing/Hasher.cs

@@ -28 +28 @@
 
 namespace HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration {
+
   [StorableClass]
   public abstract class Hasher<THashType> : DeepCloneable {
+    protected struct HashItem : IComparable<HashItem>, IEquatable<HashItem> {
+      public THashType Value { get; private set; }
+      public Symbol Symbol { get; private set; }
+
+      public int CompareTo(HashItem other) {
+        var res = Symbol.CompareTo(other.Symbol);
+        return res == 0 ? Comparer<THashType>.Default.Compare(Value, other.Value) : res;
+      }
+
+      private HashItem(THashType h, Symbol s) {
+        Value = h;
+        Symbol = s;
+      }
+
+      public static HashItem Create(THashType h, Symbol s) {
+        return new HashItem(h, s);
+      }
+
+      public bool Equals(HashItem other) {
+        return Symbol.Equals(other.Symbol) && Value.Equals(other.Value);
+      }
+    }
     protected Hasher(Grammar grammar) {
       Grammar = grammar;
@@ -41 +64 @@
     protected Grammar Grammar { get; private set; }
 
-    protected abstract THashType AggregateHashes(Symbol operatorSym, IList<THashType> hashes);
+    protected abstract HashItem AggregateHashes(Symbol operatorSym, IList<HashItem> hashes);
 
     public int CalcHashCode(SymbolList sentence) {
@@ -49 +72 @@
 
       Symbol peek = parseStack.Peek();
-      return AggregateHashes(peek, GetSubtreeHashes(parseStack)).GetHashCode();
+      return AggregateHashes(peek, GetSubtreeHashes(parseStack)).Value.GetHashCode();
     }
 
@@ -55 +78 @@
     protected Hasher(bool deserializing) { }
 
-    private IList<THashType> GetSubtreeHashes(Stack<Symbol> parseStack) {
+    private IList<HashItem> GetSubtreeHashes(Stack<Symbol> parseStack) {
       Symbol currentSymbol = parseStack.Pop();
 
@@ -72 +95 @@
           currentSymbol == Grammar.Sin || currentSymbol == Grammar.Inv) {
         // Directly aggregate the single subtree
-        return new[] { AggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack)) };
+        return new[] { AggregateHashes(currentSymbol, GetSubtreeHashes(parseStack)) };
       }
 
       // var, const or nonterminal symbol
-      return new[] { AggregateHashes(currentSymbol, new THashType[0]) };
-    }
-
-    private void AddAdditionChildHashes(HashSet<THashType> hashSet, Stack<Symbol> symbolStack) {
+      return new[] { AggregateHashes(currentSymbol, new HashItem[0]) };
+    }
+
+    private void AddAdditionChildHashes(HashSet<HashItem> hashSet, Stack<Symbol> symbolStack) {
       var peek = symbolStack.Peek();
       var hashes = GetSubtreeHashes(symbolStack); // will pop the stack
@@ -89 +112 @@
     }
 
-    private IList<THashType> GetAdditionSubtreeHashes(Stack<Symbol> parseStack) {
-      var uniqueChildHashes = new HashSet<THashType>();
+    private IList<HashItem> GetAdditionSubtreeHashes(Stack<Symbol> parseStack) {
+      var uniqueChildHashes = new HashSet<HashItem>();
 
       AddAdditionChildHashes(uniqueChildHashes, parseStack); // first child 
@@ -100 +123 @@
     }
 
-    private void AddMultiplicationChildHashes(List<THashType> hashList, Stack<Symbol> symbolStack) {
+    private void AddMultiplicationChildHashes(List<HashItem> hashList, Stack<Symbol> symbolStack) {
       var peek = symbolStack.Peek();
       var hashes = GetSubtreeHashes(symbolStack);
@@ -109 +132 @@
     }
 
-    public IList<THashType> GetMultiplicationSubtreeHashes(Stack<Symbol> parseStack) {
-      var childHashes = new List<THashType>();
+    private IList<HashItem> GetMultiplicationSubtreeHashes(Stack<Symbol> parseStack) {
+      var childHashes = new List<HashItem>();
 
       AddMultiplicationChildHashes(childHashes, parseStack); // first child
@@ -159 +182 @@
     protected IntHasher(bool deserializing) : base(deserializing) { }
 
-    protected override int AggregateHashes(Symbol operatorSym, IList<int> hashes) {
+    protected override HashItem AggregateHashes(Symbol operatorSym, IList<HashItem> hashes) {
       int start;
       if ((operatorSym == Grammar.Addition || operatorSym == Grammar.Multiplication) && hashes.Count <= 1) {
@@ -165 +188 @@
 
       } else if (operatorSym is NonterminalSymbol || operatorSym is VariableTerminalSymbol) {
-        return operatorSym.StringRepresentation.GetHashCode();
+        return HashItem.Create(operatorSym.StringRepresentation.GetHashCode(), operatorSym);
 
       } else {
@@ -172 +195 @@
 
       for (int i = 0; i < hashes.Count; i++) {
-        start = ((start << 5) + start) ^ hashes[i];
-      }
-      return start;
+        start = ((start << 5) + start) ^ hashes[i].Value;
+      }
+      return HashItem.Create(start, operatorSym);
     }
   }
@@ -191 +214 @@
     protected StringHasher(bool deserializing) : base(deserializing) { }
 
-    protected override string AggregateHashes(Symbol operatorSym, IList<string> hashes) {
+    protected override HashItem AggregateHashes(Symbol operatorSym, IList<HashItem> hashes) {
       var hashesArray = hashes.ToArray();
 
@@ -198 +221 @@
       }
       if (operatorSym is NonterminalSymbol || operatorSym is VariableTerminalSymbol) {
-        return operatorSym.StringRepresentation;
-      }
-
-      return $"[{operatorSym.StringRepresentation} ° {string.Join(" ° ", hashesArray)}]";
+        return HashItem.Create(operatorSym.StringRepresentation, operatorSym);
+      }
+
+      return HashItem.Create($"[{operatorSym.StringRepresentation} ° {string.Join(" ° ", hashesArray.Select(x => x.Value))}]", operatorSym);
     }
   }