Changeset 16979

Timestamp:

05/22/19 14:19:17 (6 years ago)

Author:

bburlacu

Message:

#2950: Simplify symbol comparison (use only calculated hash value). Run simplification in a loop (successive simplification steps until no more changes).

File:

• trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing/HashExtensions.cs (modified) (4 diffs)

trunk/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Hashing/HashExtensions.cs

@@ -22 +22 @@
 using System;
 using System.Collections.Generic;
+using System.Linq;
 
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
@@ -49 +50 @@
 
       public int CompareTo(HashNode<T> other) {
-        var res = Comparer.Compare(Data, other.Data);
-        return res == 0 ? CalculatedHashValue.CompareTo(other.CalculatedHashValue) : res;
+        return CalculatedHashValue.CompareTo(other.CalculatedHashValue);
       }
 
@@ -103 +103 @@
 
     public static HashNode<T>[] Simplify<T>(this HashNode<T>[] nodes, Func<byte[], ulong> hashFunction) where T : class {
-      var reduced = nodes.UpdateNodeSizes().Reduce().Sort(hashFunction);
-
-      for (int i = 0; i < reduced.Length; ++i) {
-        var node = reduced[i];
-        if (node.IsLeaf) {
-          continue;
-        }
-        node.Simplify?.Invoke(ref reduced, i);
-      }
-      // detect if anything was simplified
-      var count = 0;
-      foreach (var node in reduced) {
-        if (!node.Enabled) { ++count; }
-      }
-      if (count == 0) {
-        return reduced;
-      }
-
-      var simplified = new HashNode<T>[reduced.Length - count];
-      int j = 0;
-      foreach (var node in reduced) {
-        if (node.Enabled) {
-          simplified[j++] = node;
-        }
-      }
-      return simplified.UpdateNodeSizes().Reduce().Sort(hashFunction);
+      bool simplified = false;
+      nodes = nodes.UpdateNodeSizes().Reduce().Sort(hashFunction);
+      do {
+        if (simplified) {
+          simplified = false;
+          nodes = nodes.Where(x => x.Enabled).ToArray().UpdateNodeSizes().Reduce().Sort(hashFunction);
+        }
+
+        for (int i = 0; i < nodes.Length; ++i) {
+          var node = nodes[i];
+          if (node.IsLeaf) {
+            continue;
+          }
+          node.Simplify?.Invoke(ref nodes, i);
+          for (int j = i - node.Size; j < i; ++j) {
+            // detect if anything was simplified
+            if (!nodes[j].Enabled) {
+              simplified = true;
+              break;
+            }
+          }
+        }
+      } while (simplified);
+      return nodes.UpdateNodeSizes().Sort(hashFunction);
     }
 
@@ -207 +205 @@
     }
 
-    private static HashNode<T>[] Reduce<T>(this HashNode<T>[] nodes) where T : class {
+    public static HashNode<T>[] Reduce<T>(this HashNode<T>[] nodes) where T : class {
       int count = 0;
       for (int i = 0; i < nodes.Length; ++i) {