Free cookie consent management tool by TermsFeed Policy Generator

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

Last change on this file since 16260 was 16260, checked in by bburlacu, 6 years ago

#2950: Refactor HashExtensions: simplify Reduce method.

File size: 7.1 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
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;
23using System.Collections.Generic;
24
25namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
26  public static class SymbolicExpressionHashExtensions {
27    public sealed class HashNode<T> : IComparable<HashNode<T>>, IEquatable<HashNode<T>> where T : class {
28      public T Data;
29      public int Arity;
30      public int Size;
31      public bool IsCommutative;
32
33      public bool Enabled;
34      public int HashValue;           // the initial (fixed) hash value for this individual node/data
35      public int CalculatedHashValue; // the calculated hash value (taking into account the children hash values)
36
37      public Action<HashNode<T>[], int> Simplify;
38      public IComparer<T> Comparer;
39
40      public bool IsChild => Arity == 0;
41
42      public HashNode(IComparer<T> comparer) {
43        Comparer = comparer;
44      }
45
46      private HashNode() { }
47
48      public int CompareTo(HashNode<T> other) {
49        var res = Comparer.Compare(Data, other.Data);
50        return res == 0 ? CalculatedHashValue.CompareTo(other.CalculatedHashValue) : res;
51      }
52
53      public override string ToString() {
54        return $"{Data} {Arity} {Size} {CalculatedHashValue} {Enabled}";
55      }
56
57      public bool Equals(HashNode<T> other) {
58        return CalculatedHashValue.Equals(other.CalculatedHashValue);
59      }
60
61      public override bool Equals(object obj) {
62        var other = obj as HashNode<T>;
63        if (other != null)
64          return Equals(other);
65        return base.Equals(obj);
66      }
67
68      public override int GetHashCode() {
69        return CalculatedHashValue;
70      }
71
72      public static bool operator ==(HashNode<T> a, HashNode<T> b) {
73        return a.Equals(b);
74      }
75
76      public static bool operator !=(HashNode<T> a, HashNode<T> b) {
77        return !a.Equals(b);
78      }
79    }
80
81    public static int ComputeHash<T>(this HashNode<T>[] nodes, int i) where T : class {
82      var node = nodes[i];
83      var hashes = new int[node.Arity + 1];
84      int idx = 0;
85      foreach (int c in nodes.IterateChildren(i)) {
86        hashes[idx++] = nodes[c].CalculatedHashValue;
87      }
88      hashes[idx] = node.HashValue;
89      return HashUtil.JSHash(hashes);
90    }
91
92    public static HashNode<T>[] Simplify<T>(this HashNode<T>[] nodes) where T : class {
93      var reduced = nodes.UpdateNodeSizes().Reduce().Sort();
94
95      for (int i = 0; i < reduced.Length; ++i) {
96        var node = reduced[i];
97        if (node.IsChild) {
98          continue;
99        }
100        node.Simplify?.Invoke(reduced, i);
101      }
102      // detect if anything was simplified
103      var count = 0;
104      foreach (var node in reduced) {
105        if (!node.Enabled) { ++count; }
106      }
107      if (count == 0) {
108        return reduced;
109      }
110
111      var simplified = new HashNode<T>[reduced.Length - count];
112      int j = 0;
113      foreach (var node in reduced) {
114        if (node.Enabled) {
115          simplified[j++] = node;
116        }
117      }
118      return simplified.UpdateNodeSizes().Reduce().Sort();
119    }
120
121    public static HashNode<T>[] Sort<T>(this HashNode<T>[] nodes) where T : class {
122      int sort(int a, int b) => nodes[a].CompareTo(nodes[b]);
123
124      for (int i = 0; i < nodes.Length; ++i) {
125        var node = nodes[i];
126
127        if (node.IsChild) {
128          continue;
129        }
130
131        if (node.IsCommutative) { // only sort when the argument order does not matter
132          var arity = node.Arity;
133          var size = node.Size;
134
135          if (arity == size) { // all child nodes are terminals
136            Array.Sort(nodes, i - size, size);
137          } else { // i have some non-terminal children
138            var sorted = new HashNode<T>[size];
139            var indices = nodes.IterateChildren(i);
140            Array.Sort(indices, sort);
141
142            int idx = 0;
143            foreach (var j in indices) {
144              var child = nodes[j];
145              if (!child.IsChild) { // must copy complete subtree
146                Array.Copy(nodes, j - child.Size, sorted, idx, child.Size);
147                idx += child.Size;
148              }
149              sorted[idx++] = nodes[j];
150            }
151            Array.Copy(sorted, 0, nodes, i - size, size);
152          }
153        }
154        node.CalculatedHashValue = nodes.ComputeHash(i);
155      }
156      return nodes;
157    }
158
159    /// <summary>
160    /// Get a function node's child indices from left to right
161    /// </summary>
162    /// <typeparam name="T">The data type encapsulated by a hash node</typeparam>
163    /// <param name="nodes">An array of hash nodes with up-to-date node sizes</param>
164    /// <param name="i">The index in the array of hash nodes of the node whose children we want to iterate</param>
165    /// <returns>An array containing child indices</returns>
166    public static int[] IterateChildren<T>(this HashNode<T>[] nodes, int i) where T : class {
167      var node = nodes[i];
168      var arity = node.Arity;
169      var children = new int[arity];
170      var idx = i - 1;
171      for (int j = 0; j < arity; ++j) {
172        children[j] = idx;
173        idx -= 1 + nodes[idx].Size;
174      }
175      return children;
176    }
177
178    public static HashNode<T>[] UpdateNodeSizes<T>(this HashNode<T>[] nodes) where T : class {
179      for (int i = 0; i < nodes.Length; ++i) {
180        var node = nodes[i];
181        if (node.IsChild) {
182          node.Size = 0;
183          continue;
184        }
185        node.Size = node.Arity;
186        foreach (int j in nodes.IterateChildren(i)) {
187          node.Size += nodes[j].Size;
188        }
189      }
190      return nodes;
191    }
192
193    private static HashNode<T>[] Reduce<T>(this HashNode<T>[] nodes) where T : class {
194      int count = 0;
195      for (int i = 0; i < nodes.Length; ++i) {
196        var node = nodes[i];
197        if (node.IsChild || !node.IsCommutative) {
198          continue;
199        }
200
201        foreach (var j in nodes.IterateChildren(i)) {
202          if (node.HashValue == nodes[j].HashValue) {
203            nodes[j].Enabled = false;
204            node.Arity += nodes[j].Arity - 1;
205            ++count;
206          }
207        }
208      }
209      if (count == 0)
210        return nodes;
211
212      var reduced = new HashNode<T>[nodes.Length - count];
213      var idx = 0;
214      foreach (var node in nodes) {
215        if (node.Enabled) { reduced[idx++] = node; }
216      }
217      return reduced.UpdateNodeSizes();
218    }
219  }
220}
Note: See TracBrowser for help on using the repository browser.