Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing/HashExtensions.cs @ 17076

Last change on this file since 17076 was 17076, checked in by gkronber, 5 years ago

#2950: made some small changes while reviewing.

File size: 8.5 KB
RevLine 
[16218]1#region License Information
2/* HeuristicLab
[16565]3 * Copyright (C) 2002-2019 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
[16218]4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
[16979]23using System.Linq;
[16218]24
25namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
26  public static class SymbolicExpressionHashExtensions {
[17076]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>
[16218]31    public sealed class HashNode<T> : IComparable<HashNode<T>>, IEquatable<HashNode<T>> where T : class {
32      public T Data;
33      public int Arity;
34      public int Size;
35      public bool IsCommutative;
36
37      public bool Enabled;
[16263]38      public ulong HashValue;           // the initial (fixed) hash value for this individual node/data
39      public ulong CalculatedHashValue; // the calculated hash value (taking into account the children hash values)
[16218]40
[16305]41      public delegate void SimplifyAction(ref HashNode<T>[] nodes, int i);
42      public SimplifyAction Simplify;
43
[16267]44      public bool IsLeaf => Arity == 0;
[16218]45
46      public int CompareTo(HashNode<T> other) {
[16979]47        return CalculatedHashValue.CompareTo(other.CalculatedHashValue);
[16218]48      }
49
50      public override string ToString() {
51        return $"{Data} {Arity} {Size} {CalculatedHashValue} {Enabled}";
52      }
53
54      public bool Equals(HashNode<T> other) {
55        return CalculatedHashValue.Equals(other.CalculatedHashValue);
56      }
57
58      public override bool Equals(object obj) {
59        var other = obj as HashNode<T>;
60        if (other != null)
61          return Equals(other);
62        return base.Equals(obj);
63      }
64
65      public override int GetHashCode() {
[16272]66        return (int)CalculatedHashValue;
[16218]67      }
68
69      public static bool operator ==(HashNode<T> a, HashNode<T> b) {
70        return a.Equals(b);
71      }
72
73      public static bool operator !=(HashNode<T> a, HashNode<T> b) {
74        return !a.Equals(b);
75      }
76    }
77
[16272]78    public static ulong ComputeHash<T>(this HashNode<T>[] nodes, int i, Func<byte[], ulong> hashFunction) where T : class {
[16218]79      var node = nodes[i];
[16272]80      const int size = sizeof(ulong);
[16273]81      var hashes = new ulong[node.Arity + 1];
82      var bytes = new byte[(node.Arity + 1) * size];
[16272]83
84      for (int j = i - 1, k = 0; k < node.Arity; ++k, j -= 1 + nodes[j].Size) {
[16273]85        hashes[k] = nodes[j].CalculatedHashValue;
[16218]86      }
[16273]87      hashes[node.Arity] = node.HashValue;
88      Buffer.BlockCopy(hashes, 0, bytes, 0, bytes.Length);
89      return hashFunction(bytes);
[16218]90    }
91
[16272]92    // set the enabled state for the whole subtree rooted at this node
93    public static void SetEnabled<T>(this HashNode<T>[] nodes, int i, bool enabled) where T : class {
94      nodes[i].Enabled = enabled;
95      for (int j = i - nodes[i].Size; j < i; ++j)
96        nodes[j].Enabled = enabled;
97    }
[16218]98
[16272]99    public static HashNode<T>[] Simplify<T>(this HashNode<T>[] nodes, Func<byte[], ulong> hashFunction) where T : class {
[16979]100      bool simplified = false;
101      nodes = nodes.UpdateNodeSizes().Reduce().Sort(hashFunction);
102      do {
103        if (simplified) {
104          simplified = false;
105          nodes = nodes.Where(x => x.Enabled).ToArray().UpdateNodeSizes().Reduce().Sort(hashFunction);
[16218]106        }
107
[16979]108        for (int i = 0; i < nodes.Length; ++i) {
109          var node = nodes[i];
110          if (node.IsLeaf) {
111            continue;
112          }
113          node.Simplify?.Invoke(ref nodes, i);
114          for (int j = i - node.Size; j < i; ++j) {
115            // detect if anything was simplified
116            if (!nodes[j].Enabled) {
117              simplified = true;
118              break;
119            }
120          }
[16218]121        }
[16979]122      } while (simplified);
123      return nodes.UpdateNodeSizes().Sort(hashFunction);
[16218]124    }
125
[16272]126    public static HashNode<T>[] Sort<T>(this HashNode<T>[] nodes, Func<byte[], ulong> hashFunction) where T : class {
[16255]127      int sort(int a, int b) => nodes[a].CompareTo(nodes[b]);
128
[16218]129      for (int i = 0; i < nodes.Length; ++i) {
130        var node = nodes[i];
131
[16267]132        if (node.IsLeaf) {
[16218]133          continue;
134        }
135
136        if (node.IsCommutative) { // only sort when the argument order does not matter
137          var arity = node.Arity;
138          var size = node.Size;
139
140          if (arity == size) { // all child nodes are terminals
141            Array.Sort(nodes, i - size, size);
142          } else { // i have some non-terminal children
143            var sorted = new HashNode<T>[size];
[16261]144            var indices = new int[node.Arity];
145            for (int j = i - 1, k = 0; k < node.Arity; j -= 1 + nodes[j].Size, ++k) {
146              indices[k] = j;
147            }
[16255]148            Array.Sort(indices, sort);
[16218]149
150            int idx = 0;
151            foreach (var j in indices) {
152              var child = nodes[j];
[16267]153              if (!child.IsLeaf) { // must copy complete subtree
[16218]154                Array.Copy(nodes, j - child.Size, sorted, idx, child.Size);
155                idx += child.Size;
156              }
157              sorted[idx++] = nodes[j];
158            }
159            Array.Copy(sorted, 0, nodes, i - size, size);
160          }
161        }
[16272]162        node.CalculatedHashValue = nodes.ComputeHash(i, hashFunction);
[16218]163      }
[16252]164      return nodes;
[16218]165    }
166
167    /// <summary>
[17076]168    /// Get a function node's child indices
[16218]169    /// </summary>
[16252]170    /// <typeparam name="T">The data type encapsulated by a hash node</typeparam>
[17076]171    /// <param name="nodes">An array of hash nodes with up-to-date node sizes (see UpdateNodeSizes)</param>
[16252]172    /// <param name="i">The index in the array of hash nodes of the node whose children we want to iterate</param>
[16218]173    /// <returns>An array containing child indices</returns>
174    public static int[] IterateChildren<T>(this HashNode<T>[] nodes, int i) where T : class {
175      var node = nodes[i];
176      var arity = node.Arity;
177      var children = new int[arity];
178      var idx = i - 1;
179      for (int j = 0; j < arity; ++j) {
180        children[j] = idx;
181        idx -= 1 + nodes[idx].Size;
182      }
183      return children;
184    }
185
[17076]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>
[16252]192    public static HashNode<T>[] UpdateNodeSizes<T>(this HashNode<T>[] nodes) where T : class {
[16218]193      for (int i = 0; i < nodes.Length; ++i) {
194        var node = nodes[i];
[16267]195        if (node.IsLeaf) {
[16218]196          node.Size = 0;
197          continue;
198        }
199        node.Size = node.Arity;
[17076]200        // visit all children and sum up their size (assumes postfix order).
[16261]201        for (int j = i - 1, k = 0; k < node.Arity; j -= 1 + nodes[j].Size, ++k) {
[16218]202          node.Size += nodes[j].Size;
203        }
204      }
[16252]205      return nodes;
[16218]206    }
207
[17076]208    // disables duplicate branches and removes the disabled nodes
[16979]209    public static HashNode<T>[] Reduce<T>(this HashNode<T>[] nodes) where T : class {
[16260]210      int count = 0;
211      for (int i = 0; i < nodes.Length; ++i) {
212        var node = nodes[i];
[16267]213        if (node.IsLeaf || !node.IsCommutative) {
[16260]214          continue;
215        }
[16218]216
[16261]217        var arity = node.Arity;
218        for (int j = i - 1, k = 0; k < arity; j -= 1 + nodes[j].Size, ++k) {
[16260]219          if (node.HashValue == nodes[j].HashValue) {
220            nodes[j].Enabled = false;
221            node.Arity += nodes[j].Arity - 1;
222            ++count;
223          }
224        }
[16218]225      }
226      if (count == 0)
227        return nodes;
228
229      var reduced = new HashNode<T>[nodes.Length - count];
[16260]230      var idx = 0;
[16218]231      foreach (var node in nodes) {
[16260]232        if (node.Enabled) { reduced[idx++] = node; }
[16218]233      }
[16252]234      return reduced.UpdateNodeSizes();
[16218]235    }
236  }
237}
Note: See TracBrowser for help on using the repository browser.