Changeset 15835


Ignore:
Timestamp:
03/09/18 14:31:15 (3 years ago)
Author:
lkammere
Message:

#2886: Split huge hashing function into smaller ones.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Hashing/Hasher.cs

    r15832 r15835  
    2828      // ADDITION
    2929      if (currentSymbol == Grammar.Addition) {
    30         var uniqueChildHashes = new HashSet<THashType>();
    31 
    32         // First subtree
    33         if (parseStack.Peek() == Grammar.Addition) {
    34           uniqueChildHashes.UnionWith(GetSubtreeHashes(parseStack));
    35         } else {
    36           var peek = parseStack.Peek();
    37           uniqueChildHashes.Add(AggregateHashes(peek, GetSubtreeHashes(parseStack)));
    38         }
    39         // Second subtree
    40         if (parseStack.Peek() == Grammar.Addition) {
    41           uniqueChildHashes.UnionWith(GetSubtreeHashes(parseStack));
    42         } else {
    43           var peek = parseStack.Peek();
    44           uniqueChildHashes.Add(AggregateHashes(peek, GetSubtreeHashes(parseStack)));
    45         }
    46 
    47         var result = uniqueChildHashes.ToArray();
    48         Array.Sort(result);
    49         return result;
     30        return GetAdditionSubtreeHashes(parseStack);
    5031      }
    5132
    5233      // MULTIPLICATION
    5334      if (currentSymbol == Grammar.Multiplication) {
    54         var childHashes = new List<THashType>();
    55 
    56         // First subtree
    57         if (parseStack.Peek() == Grammar.Multiplication) {
    58           childHashes.AddRange(GetSubtreeHashes(parseStack));
    59         } else {
    60           childHashes.Add(AggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack)));
    61         }
    62         // Second subtree
    63         if (parseStack.Peek() == Grammar.Multiplication) {
    64           childHashes.AddRange(GetSubtreeHashes(parseStack));
    65         } else {
    66           childHashes.Add(AggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack)));
    67         }
    68 
    69         // Sort due to commutativity
    70         childHashes.Sort();
    71 
    72         // Cancel out inverse factors.
    73         bool[] isFactorRemaining = Enumerable.Repeat(true, childHashes.Count).ToArray();
    74 
    75         for (int i = 0; i < isFactorRemaining.Length; i++) {
    76           if (!isFactorRemaining[i]) continue;
    77           if (isFactorRemaining.Length <= 2) break; // Until we have constants, we can't cancel out all terms.
    78 
    79           var currFactor = childHashes[i];
    80           var invFactor = AggregateHashes(Grammar.Inv, new[] { currFactor });
    81 
    82           int indexOfInv = childHashes.IndexOf(invFactor);
    83           if (indexOfInv >= 0 && isFactorRemaining[indexOfInv]) {
    84             isFactorRemaining[i] = isFactorRemaining[indexOfInv] = false;
    85           }
    86         }
    87 
    88         return childHashes
    89           .Where((c, i) => isFactorRemaining[i])
    90           .ToArray();
     35        return GetMultiplicationSubtreeHashes(parseStack);
    9136      }
    9237
     
    9540          currentSymbol == Grammar.Sin || currentSymbol == Grammar.Cos ||
    9641          currentSymbol == Grammar.Inv) {
     42        // Directly aggregate the single subtree
    9743        return new[] { AggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack)) };
    9844      }
     
    10147      return new[] { AggregateHashes(currentSymbol, new THashType[0]) };
    10248    }
     49
     50    private THashType[] GetAdditionSubtreeHashes(Stack<Symbol> parseStack) {
     51      var uniqueChildHashes = new HashSet<THashType>();
     52
     53      // First subtree
     54      if (parseStack.Peek() == Grammar.Addition) {
     55        uniqueChildHashes.UnionWith(GetSubtreeHashes(parseStack));
     56      } else {
     57        var peek = parseStack.Peek();
     58        uniqueChildHashes.Add(AggregateHashes(peek, GetSubtreeHashes(parseStack)));
     59      }
     60      // Second subtree
     61      if (parseStack.Peek() == Grammar.Addition) {
     62        uniqueChildHashes.UnionWith(GetSubtreeHashes(parseStack));
     63      } else {
     64        var peek = parseStack.Peek();
     65        uniqueChildHashes.Add(AggregateHashes(peek, GetSubtreeHashes(parseStack)));
     66      }
     67
     68      var result = uniqueChildHashes.ToArray();
     69      Array.Sort(result);
     70      return result;
     71    }
     72
     73    public THashType[] GetMultiplicationSubtreeHashes(Stack<Symbol> parseStack) {
     74      var childHashes = new List<THashType>();
     75
     76      // First subtree
     77      if (parseStack.Peek() == Grammar.Multiplication) {
     78        childHashes.AddRange(GetSubtreeHashes(parseStack));
     79      } else {
     80        childHashes.Add(AggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack)));
     81      }
     82      // Second subtree
     83      if (parseStack.Peek() == Grammar.Multiplication) {
     84        childHashes.AddRange(GetSubtreeHashes(parseStack));
     85      } else {
     86        childHashes.Add(AggregateHashes(parseStack.Peek(), GetSubtreeHashes(parseStack)));
     87      }
     88
     89      // Sort due to commutativity
     90      childHashes.Sort();
     91
     92      // Cancel out inverse factors.
     93      bool[] isFactorRemaining = Enumerable.Repeat(true, childHashes.Count).ToArray();
     94
     95      for (int i = 0; i < isFactorRemaining.Length; i++) {
     96        if (!isFactorRemaining[i]) continue;
     97        if (isFactorRemaining.Length <= 2) break; // Until we have constants, we can't cancel out all terms.
     98
     99        var currFactor = childHashes[i];
     100        var invFactor = AggregateHashes(Grammar.Inv, new[] { currFactor });
     101
     102        int indexOfInv = childHashes.IndexOf(invFactor);
     103        if (indexOfInv >= 0 && isFactorRemaining[indexOfInv]) {
     104          isFactorRemaining[i] = isFactorRemaining[indexOfInv] = false;
     105        }
     106      }
     107
     108      return childHashes
     109        .Where((c, i) => isFactorRemaining[i])
     110        .ToArray();
     111    }
     112
     113
    103114  }
    104115
Note: See TracChangeset for help on using the changeset viewer.