Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
07/05/19 10:26:41 (5 years ago)
Author:
gkronber
Message:

#2950: made some small changes while reviewing.

Location:
trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing/HashExtensions.cs

    r16983 r17076  
    2525namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
    2626  public static class SymbolicExpressionHashExtensions {
     27    /// <summary>
     28    /// Holds data that is necessary to handle tree nodes in hashing / simplification.
     29    /// </summary>
     30    /// <typeparam name="T">The tree node type</typeparam>
    2731    public sealed class HashNode<T> : IComparable<HashNode<T>>, IEquatable<HashNode<T>> where T : class {
    2832      public T Data;
     
    3842      public SimplifyAction Simplify;
    3943
    40       //public IComparer<T> Comparer;
    41 
    4244      public bool IsLeaf => Arity == 0;
    43 
    44       //public HashNode(IComparer<T> comparer) {
    45       //  Comparer = comparer;
    46       //}
    47 
    48       //public HashNode() { }
    4945
    5046      public int CompareTo(HashNode<T> other) {
     
    170166
    171167    /// <summary>
    172     /// Get a function node's child indicest
     168    /// Get a function node's child indices
    173169    /// </summary>
    174170    /// <typeparam name="T">The data type encapsulated by a hash node</typeparam>
    175     /// <param name="nodes">An array of hash nodes with up-to-date node sizes</param>
     171    /// <param name="nodes">An array of hash nodes with up-to-date node sizes (see UpdateNodeSizes)</param>
    176172    /// <param name="i">The index in the array of hash nodes of the node whose children we want to iterate</param>
    177173    /// <returns>An array containing child indices</returns>
     
    188184    }
    189185
     186    /// <summary>
     187    /// Determines size of each branch and sets the results for each node.
     188    /// </summary>
     189    /// <typeparam name="T">The data type encapsulated by a hash node</typeparam>
     190    /// <param name="nodes">An array of hash nodes in postfix order.</param>
     191    /// <returns>The array with updated node sizes. The array is not copied.</returns>
    190192    public static HashNode<T>[] UpdateNodeSizes<T>(this HashNode<T>[] nodes) where T : class {
    191193      for (int i = 0; i < nodes.Length; ++i) {
     
    196198        }
    197199        node.Size = node.Arity;
    198 
     200        // visit all children and sum up their size (assumes postfix order).
    199201        for (int j = i - 1, k = 0; k < node.Arity; j -= 1 + nodes[j].Size, ++k) {
    200202          node.Size += nodes[j].Size;
     
    204206    }
    205207
     208    // disables duplicate branches and removes the disabled nodes
    206209    public static HashNode<T>[] Reduce<T>(this HashNode<T>[] nodes) where T : class {
    207210      int count = 0;
  • trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing/SymbolicExpressionTreeHash.cs

    r16983 r17076  
    4848      ulong hashFunction(byte[] input) => HashUtil.DJBHash(input);
    4949
    50       var hashNodes = simplify ? node.MakeNodes(strict).Simplify(hashFunction) : node.MakeNodes(strict).Sort(hashFunction);
     50      var hashNodes = simplify ? node.MakeNodes(strict).Simplify(hashFunction) : node.MakeNodes(strict).Sort(hashFunction); // simplify sorts implicitly
    5151      var hashes = new ulong[hashNodes.Length];
    5252      for (int i = 0; i < hashes.Length; ++i) {
     
    210210      var treeNodes = nodes.Select(x => x.Data.Symbol.CreateTreeNode()).ToArray();
    211211
     212      // construct tree top down (assumes postfix order for nodes)
    212213      for (int i = nodes.Length - 1; i >= 0; --i) {
    213214        var node = nodes[i];
     
    244245    // (in other words simplification should be applied in a bottom-up fashion)
    245246    public static ISymbolicExpressionTree Simplify(ISymbolicExpressionTree tree) {
    246       ulong hashFunction(byte[] bytes) => HashUtil.JSHash(bytes);
    247       var root = tree.Root.GetSubtree(0).GetSubtree(0);
     247      ulong hashFunction(byte[] bytes) => HashUtil.DJBHash(bytes);
     248      var root = tree.ActualRoot();
    248249      var nodes = root.MakeNodes();
    249250      var simplified = nodes.Simplify(hashFunction);
     
    369370        nodes[i].Enabled = false;
    370371      } else if ((parentSymbol is Exponential && childSymbol is Logarithm) || (parentSymbol is Logarithm && childSymbol is Exponential)) {
     372        // exp(log(x)) == x only for positive x. We consider this as equivalent for hashing anyway.
    371373        child.Enabled = parent.Enabled = false;
    372374      }
Note: See TracChangeset for help on using the changeset viewer.