Changeset 15965

Timestamp:

06/19/18 10:57:47 (7 years ago)

Author:

bburlacu

Message:

#2886: Improve hashing performance (about 10% measured improvement)

File:

• branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Hashing/Hasher.cs (modified) (8 diffs)

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

@@ -19 +19 @@
     protected Grammar Grammar { get; }
 
-    protected abstract THashType AggregateHashes(Symbol operatorSym, THashType[] hashes);
+    protected abstract THashType AggregateHashes(Symbol operatorSym, IList<THashType> hashes);
 
     public int CalcHashCode(SymbolString sentence) {
@@ -33 +33 @@
     protected Hasher(bool deserializing) { }
 
-    private THashType[] GetSubtreeHashes(Stack<Symbol> parseStack) {
+    private IList<THashType> GetSubtreeHashes(Stack<Symbol> parseStack) {
       Symbol currentSymbol = parseStack.Pop();
 
@@ -57 +57 @@
     }
 
-    private THashType[] GetAdditionSubtreeHashes(Stack<Symbol> parseStack) {
+    private void AddAdditionChildHashes(HashSet<THashType> hashSet, Stack<Symbol> symbolStack) {
+      var peek = symbolStack.Peek();
+      var hashes = GetSubtreeHashes(symbolStack); // will pop the stack
+
+      if (peek == Grammar.Addition)
+        hashSet.UnionWith(hashes);
+      else
+        hashSet.Add(AggregateHashes(peek, hashes));
+    }
+
+    private IList<THashType> GetAdditionSubtreeHashes(Stack<Symbol> parseStack) {
       var uniqueChildHashes = new HashSet<THashType>();
 
-      // First subtree
-      if (parseStack.Peek() == Grammar.Addition) {
-        uniqueChildHashes.UnionWith(GetSubtreeHashes(parseStack));
-      } else {
-        var peek = parseStack.Peek();
-        uniqueChildHashes.Add(AggregateHashes(peek, GetSubtreeHashes(parseStack)));
-      }
-      // Second subtree
-      if (parseStack.Peek() == Grammar.Addition) {
-        uniqueChildHashes.UnionWith(GetSubtreeHashes(parseStack));
-      } else {
-        var peek = parseStack.Peek();
-        uniqueChildHashes.Add(AggregateHashes(peek, GetSubtreeHashes(parseStack)));
-      }
+      AddAdditionChildHashes(uniqueChildHashes, parseStack); // first child 
+      AddAdditionChildHashes(uniqueChildHashes, parseStack); // second child 
 
       var result = uniqueChildHashes.ToArray();
@@ -80 +78 @@
     }
 
-    public THashType[] GetMultiplicationSubtreeHashes(Stack<Symbol> parseStack) {
+    private void AddMultiplicationChildHashes(List<THashType> hashList, Stack<Symbol> symbolStack) {
+      var peek = symbolStack.Peek();
+      var hashes = GetSubtreeHashes(symbolStack);
+      if (peek == Grammar.Multiplication)
+        hashList.AddRange(hashes);
+      else
+        hashList.Add(AggregateHashes(peek, hashes));
+    }
+
+    public IList<THashType> GetMultiplicationSubtreeHashes(Stack<Symbol> parseStack) {
       var childHashes = new List<THashType>();
 
-      // First subtree
-      if (parseStack.Peek() == Grammar.Multiplication) {
-        childHashes.AddRange(GetSubtreeHashes(parseStack));
-      } else {
-        childHashes.Add(AggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack)));
-      }
-      // Second subtree
-      if (parseStack.Peek() == Grammar.Multiplication) {
-        childHashes.AddRange(GetSubtreeHashes(parseStack));
-      } else {
-        childHashes.Add(AggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack)));
-      }
+      AddMultiplicationChildHashes(childHashes, parseStack); // first child
+      AddMultiplicationChildHashes(childHashes, parseStack); // second child
 
       // Sort due to commutativity
       childHashes.Sort();
 
+      if (childHashes.Count <= 2)
+        return childHashes;
+
       // Cancel out inverse factors.
-      bool[] isFactorRemaining = Enumerable.Repeat(true, childHashes.Count).ToArray();
-
-      for (int i = 0; i < isFactorRemaining.Length; i++) {
-        if (!isFactorRemaining[i]) continue;
-        if (isFactorRemaining.Length <= 2) break; // Until we have constants, we can't cancel out all terms.
+      var isInvFactor = new bool[childHashes.Count];
+      bool foundInvFactor = false;
+      for (int i = 0; i < isInvFactor.Length; i++) {
+        if (isInvFactor[i]) continue;
 
         var currFactor = childHashes[i];
@@ -110 +109 @@
 
         int indexOfInv = childHashes.IndexOf(invFactor);
-        if (indexOfInv >= 0 && isFactorRemaining[indexOfInv]) {
-          isFactorRemaining[i] = isFactorRemaining[indexOfInv] = false;
+        if (indexOfInv >= 0 && !isInvFactor[indexOfInv]) {
+          isInvFactor[i] = isInvFactor[indexOfInv] = true;
+          foundInvFactor = true;
         }
       }
 
+      if (!foundInvFactor)
+        return childHashes;
+
       return childHashes
-        .Where((c, i) => isFactorRemaining[i])
+        .Where((c, i) => !isInvFactor[i])
         .ToArray();
     }
@@ -134 +137 @@
     protected IntHasher(bool deserializing) : base(deserializing) { }
 
-    protected override int AggregateHashes(Symbol operatorSym, int[] hashes) {
+    protected override int AggregateHashes(Symbol operatorSym, IList<int> hashes) {
       int start;
-      if ((operatorSym == Grammar.Addition || operatorSym == Grammar.Multiplication) && hashes.Length <= 1) {
+      if ((operatorSym == Grammar.Addition || operatorSym == Grammar.Multiplication) && hashes.Count <= 1) {
         start = 0;
 
@@ -146 +149 @@
       }
 
-      for (int i = 0; i < hashes.Length; i++) {
+      for (int i = 0; i < hashes.Count; i++) {
         start = ((start << 5) + start) ^ hashes[i];
       }
@@ -166 +169 @@
     protected StringHasher(bool deserializing) : base(deserializing) { }
 
-    protected override string AggregateHashes(Symbol operatorSym, string[] hashes) {
+    protected override string AggregateHashes(Symbol operatorSym, IList<string> hashes) {
       var hashesArray = hashes.ToArray();