Changeset 16979


Ignore:
Timestamp:
05/22/19 14:19:17 (3 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:
1 edited

Legend:

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

    r16565 r16979  
    2222using System;
    2323using System.Collections.Generic;
     24using System.Linq;
    2425
    2526namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
     
    4950
    5051      public int CompareTo(HashNode<T> other) {
    51         var res = Comparer.Compare(Data, other.Data);
    52         return res == 0 ? CalculatedHashValue.CompareTo(other.CalculatedHashValue) : res;
     52        return CalculatedHashValue.CompareTo(other.CalculatedHashValue);
    5353      }
    5454
     
    103103
    104104    public static HashNode<T>[] Simplify<T>(this HashNode<T>[] nodes, Func<byte[], ulong> hashFunction) where T : class {
    105       var reduced = nodes.UpdateNodeSizes().Reduce().Sort(hashFunction);
    106 
    107       for (int i = 0; i < reduced.Length; ++i) {
    108         var node = reduced[i];
    109         if (node.IsLeaf) {
    110           continue;
    111         }
    112         node.Simplify?.Invoke(ref reduced, i);
    113       }
    114       // detect if anything was simplified
    115       var count = 0;
    116       foreach (var node in reduced) {
    117         if (!node.Enabled) { ++count; }
    118       }
    119       if (count == 0) {
    120         return reduced;
    121       }
    122 
    123       var simplified = new HashNode<T>[reduced.Length - count];
    124       int j = 0;
    125       foreach (var node in reduced) {
    126         if (node.Enabled) {
    127           simplified[j++] = node;
    128         }
    129       }
    130       return simplified.UpdateNodeSizes().Reduce().Sort(hashFunction);
     105      bool simplified = false;
     106      nodes = nodes.UpdateNodeSizes().Reduce().Sort(hashFunction);
     107      do {
     108        if (simplified) {
     109          simplified = false;
     110          nodes = nodes.Where(x => x.Enabled).ToArray().UpdateNodeSizes().Reduce().Sort(hashFunction);
     111        }
     112
     113        for (int i = 0; i < nodes.Length; ++i) {
     114          var node = nodes[i];
     115          if (node.IsLeaf) {
     116            continue;
     117          }
     118          node.Simplify?.Invoke(ref nodes, i);
     119          for (int j = i - node.Size; j < i; ++j) {
     120            // detect if anything was simplified
     121            if (!nodes[j].Enabled) {
     122              simplified = true;
     123              break;
     124            }
     125          }
     126        }
     127      } while (simplified);
     128      return nodes.UpdateNodeSizes().Sort(hashFunction);
    131129    }
    132130
     
    207205    }
    208206
    209     private static HashNode<T>[] Reduce<T>(this HashNode<T>[] nodes) where T : class {
     207    public static HashNode<T>[] Reduce<T>(this HashNode<T>[] nodes) where T : class {
    210208      int count = 0;
    211209      for (int i = 0; i < nodes.Length; ++i) {
Note: See TracChangeset for help on using the changeset viewer.