Changeset 16193

Timestamp:

09/28/18 15:22:58 (6 years ago)

Author:

bburlacu

Message:

#2886: Implement new hasher (faster & less collision prone) and update unit tests

Location:

branches/2886_SymRegGrammarEnumeration

Files:

• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Hashing/HashExtensions.cs (added)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/Hashing/HashUtil.cs (added)
• HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.csproj (modified) (1 diff)
• Test/TreeHashingTest.cs (modified) (16 diffs)

branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration.csproj

@@ -128 +128 @@
     <Compile Include="Hashing\Hasher.cs" />
     <Compile Include="GrammarEnumeration\SearchDataStructure.cs" />
+    <Compile Include="Hashing\HashExtensions.cs" />
+    <Compile Include="Hashing\HashUtil.cs" />
     <Compile Include="ProblemInstances\AircraftMaximumLift.cs" />
     <Compile Include="ProblemInstances\FluidDynamics.cs" />

branches/2886_SymRegGrammarEnumeration/Test/TreeHashingTest.cs

@@ -1 +1 @@
 using System;
 using System.Collections.Generic;
+using System.Diagnostics;
 using System.Linq;
+using System.Security.Cryptography;
 using HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration;
 using Microsoft.VisualStudio.TestTools.UnitTesting;
+using HierarchicalFormatter = HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.SymbolicExpressionTreeHierarchicalFormatter;
 
 namespace Test {
@@ -15 +18 @@
     private TerminalSymbol c;
 
+    Func<Grammar, SymbolList, int> ComputeHash = (grammar, sentence) => grammar.ComputeHash(null, sentence);
+
     [TestInitialize]
     public void InitTest() {
@@ -31 +36 @@
       SymbolList s2 = new SymbolList(new[] { varA, varB, grammar.Addition, varC, grammar.Addition });
 
-      int hash1 = grammar.Hasher.CalcHashCode(s1);
-      int hash2 = grammar.Hasher.CalcHashCode(s2);
+      int hash1 = ComputeHash(grammar, s1);
+      int hash2 = ComputeHash(grammar, s2);
 
       Assert.AreEqual(hash1, hash2);
@@ -43 +48 @@
       SymbolList s2 = new SymbolList(new[] { varB, varB, grammar.Addition, varB, grammar.Addition });
 
-      int hash1 = grammar.Hasher.CalcHashCode(s1);
-      int hash2 = grammar.Hasher.CalcHashCode(s2);
+      int hash1 = ComputeHash(grammar, s1);
+      int hash2 = ComputeHash(grammar, s2);
 
       Assert.AreNotEqual(hash1, hash2);
@@ -55 +60 @@
       SymbolList s2 = new SymbolList(new[] { varB, varA, grammar.Addition });
 
-      int hash1 = grammar.Hasher.CalcHashCode(s1);
-      int hash2 = grammar.Hasher.CalcHashCode(s2);
+      int hash1 = ComputeHash(grammar, s1);
+      int hash2 = ComputeHash(grammar, s2);
 
       Assert.AreEqual(hash1, hash2);
@@ -67 +72 @@
       SymbolList s2 = new SymbolList(new[] { varA, varB, varA, grammar.Addition, grammar.Addition });
 
-      int hash1 = grammar.Hasher.CalcHashCode(s1);
-      int hash2 = grammar.Hasher.CalcHashCode(s2);
+      int hash1 = ComputeHash(grammar, s1);
+      int hash2 = ComputeHash(grammar, s2);
 
       Assert.AreEqual(hash1, hash2);
@@ -79 +84 @@
       SymbolList s2 = new SymbolList(new[] { varA });
 
-      int hash1 = grammar.Hasher.CalcHashCode(s1);
-      int hash2 = grammar.Hasher.CalcHashCode(s2);
+      int hash1 = ComputeHash(grammar, s1);
+      int hash2 = ComputeHash(grammar, s2);
 
       Assert.AreEqual(hash1, hash2);
@@ -91 +96 @@
       SymbolList s2 = new SymbolList(new[] { varA, varA, varA, grammar.Multiplication, grammar.Addition });
 
-      int hash1 = grammar.Hasher.CalcHashCode(s1);
-      int hash2 = grammar.Hasher.CalcHashCode(s2);
+      int hash1 = ComputeHash(grammar, s1);
+      int hash2 = ComputeHash(grammar, s2);
 
       Assert.AreNotEqual(hash1, hash2);
@@ -103 +108 @@
       SymbolList s2 = new SymbolList(new Symbol[] { varA, grammar.Expr, grammar.Addition });
 
-      int hash1 = grammar.Hasher.CalcHashCode(s1);
-      int hash2 = grammar.Hasher.CalcHashCode(s2);
+      int hash1 = ComputeHash(grammar, s1);
+      int hash2 = ComputeHash(grammar, s2);
 
       Assert.AreEqual(hash1, hash2);
@@ -117 +122 @@
       SymbolList s2 = new SymbolList(new Symbol[] { varA, varB, grammar.Multiplication });
 
-      int hash1 = grammar.Hasher.CalcHashCode(s1);
-      int hash2 = grammar.Hasher.CalcHashCode(s2);
+      int hash1 = ComputeHash(grammar, s1);
+      int hash2 = ComputeHash(grammar, s2);
 
       Assert.AreEqual(hash1, hash2);
@@ -129 +134 @@
       SymbolList s2 = new SymbolList(new Symbol[] { varA, varA, varA, grammar.Multiplication, grammar.Addition, grammar.Sin, varA, grammar.Inv, varA, grammar.Sin, varA, grammar.Multiplication, grammar.Multiplication, grammar.Addition });
 
-      int hash1 = grammar.Hasher.CalcHashCode(s1);
-      int hash2 = grammar.Hasher.CalcHashCode(s2);
+      int hash1 = ComputeHash(grammar, s1);
+      int hash2 = ComputeHash(grammar, s2);
+
+      Console.WriteLine(s1);
+      Console.WriteLine(PrintTree(s1));
+      Console.WriteLine(grammar.Simplify(null, s1));
+      Console.WriteLine(hash1);
+      Console.WriteLine();
+      Console.WriteLine(s2);
+      Console.WriteLine(PrintTree(s2));
+      Console.WriteLine(grammar.Simplify(null, s2));
+      Console.WriteLine(hash2);
+
 
       Assert.AreEqual(hash1, hash2);
@@ -142 +158 @@
       SymbolList s2 = new SymbolList(new Symbol[] { c, varA, grammar.Multiplication, c, varA, grammar.Multiplication, grammar.Addition, c, grammar.Addition });
 
-      int hash1 = grammar.Hasher.CalcHashCode(s1);
-      int hash2 = grammar.Hasher.CalcHashCode(s2);
+      int hash1 = ComputeHash(grammar, s1);
+      int hash2 = ComputeHash(grammar, s2);
 
       Assert.AreEqual(hash1, hash2);
@@ -153 +169 @@
       //const int nvars = 1;
       //var variables = Enumerable.Range(1, nvars).Select(x => $"x{x}").ToArray();
+      var variables = new[] { "a", "b" };
+      var grammar = new Grammar(variables, Enum.GetValues(typeof(GrammarRule)).Cast<GrammarRule>());
+
+      Func<SymbolList, int> hash = s => grammar.Hasher.CalcHashCode(s);
+      int length = 100;
+      int depth = 20;
+
+      //List<SymbolList> sentences = EnumerateGrammarBreadth(grammar, length: length, hashPhrases: false).ToList();
+      //Console.WriteLine("Breadth: {0} generated, {1} distinct sentences", sentences.Count, sentences.GroupBy(hash).Count());
+
+      //var sentences = EnumerateGrammarBreadth(grammar, length: length, hashPhrases: true).ToList();
+      //Console.WriteLine("Breadth (hashed): {0} generated, {1} distinct sentences", sentences.Count, sentences.GroupBy(hash).Count());
+
+      var sentences = EnumerateGrammarDepth(grammar, length: length, depth: depth, hashPhrases: false).ToList();
+      Console.WriteLine("Depth: {0} generated, {1} distinct sentences", sentences.Count, sentences.GroupBy(hash).Count());
+
+      sentences = EnumerateGrammarDepth(grammar, length: length, depth: depth, hashPhrases: true).ToList();
+      Console.WriteLine("Depth (hashed): {0} generated, {1} distinct sentences", sentences.Count, sentences.GroupBy(hash).Count());
+    }
+
+    [TestMethod]
+    [TestCategory("TreeHashing")]
+    public void HashExtensionsTest() {
+      var variables = new[] { "x", "y", "z" };
+      var rules = Enum.GetValues(typeof(GrammarRule)).Cast<GrammarRule>();
+      var grammar = new Grammar(variables, rules);
+      var add = grammar.Addition;
+      var mul = grammar.Multiplication;
+      var exp = grammar.Exp;
+      var log = grammar.Log;
+      var inv = grammar.Inv;
+      var sin = grammar.Sin;
+
+      var c = grammar.Const;
+      var x = grammar.VarTerminals.Single(v => v.StringRepresentation == "x");
+      var y = grammar.VarTerminals.Single(v => v.StringRepresentation == "y");
+      var z = grammar.VarTerminals.Single(v => v.StringRepresentation == "z");
+
+
+      var ha = SHA512.Create();
+
+      var sentences = new[] {
+        new SymbolList(c, c, x, mul, c, add, inv, mul, c, add),
+        new SymbolList(c, c, x, mul, c, add, log, mul, c, add),
+        new SymbolList(x, x, add),
+        new SymbolList(x, x, add, x, add),
+        new SymbolList(x, x, add, y, add),
+        new SymbolList(x, x, add, x, add, x, add),
+        new SymbolList(x, x, add, y, add, x, add),
+        new SymbolList(x, y, mul, x, y, mul, add),
+        new SymbolList(x, y, mul, y, x, mul, add),
+        new SymbolList(x, y, mul, z, y, mul, add),
+        new SymbolList(x, x, add, y, mul),
+        new SymbolList(x, x, add, y, mul, y, mul),
+        new SymbolList(x, x, inv, mul),
+        new SymbolList(x, inv, x, inv, mul, x, mul, x, mul),
+        new SymbolList(c, x, x, x, x, x, x, mul, mul, mul, mul, mul, mul, c, x, mul, c, add, add),
+        new SymbolList(c, x, x, x, x, x, x, mul, mul, mul, mul, mul, mul, c, x, mul, c, add, add),
+        new SymbolList(c, x, mul, c, x, x, x, x, x, x, mul, mul, mul, mul, mul, mul, c, add, add),
+        new SymbolList(c, x, x, x, x, mul, mul, mul, mul, c, x, mul, c, x, mul, c, add, add, add),
+        new SymbolList(c, x, mul, c, x, x, x, x, mul, mul, mul, mul, c, x, mul, c, add, add, add)
+    };
+
+      foreach (var sentence in sentences) {
+        var simplified = grammar.Simplify(ha, sentence);
+        Console.WriteLine($"{sentence} -> {simplified} {grammar.Hasher.CalcHashCode(sentence)} {grammar.ComputeHash(ha, sentence)}");
+        Console.WriteLine();
+      }
+    }
+
+    string PrintTree(SymbolList s) {
+      var t = grammar.ParseSymbolicExpressionTree(s);
+      return HierarchicalFormatter.Format(t.Root.GetSubtree(0).GetSubtree(0));
+    }
+
+    [TestMethod]
+    [TestCategory("TreeHashing")]
+    public void HashCollisionsTest() {
       var variables = new[] { "x", "y", "z", "w" };
-      var grammar = new Grammar(variables, Enum.GetValues(typeof(GrammarRule)).Cast<GrammarRule>());
-
-      Func<SymbolList, int> hash = s => grammar.Hasher.CalcHashCode(s);
-
-      List<SymbolList> sentences = EnumerateGrammarBreadth(grammar, length: 20, hashPhrases: false).ToList();
-      Console.WriteLine("Breadth: {0} generated, {1} distinct sentences", sentences.Count, sentences.GroupBy(hash).Count());
-
-      sentences = EnumerateGrammarBreadth(grammar, length: 20, hashPhrases: true).ToList();
-      Console.WriteLine("Breadth (hashed): {0} generated, {1} distinct sentences", sentences.Count, sentences.GroupBy(hash).Count());
-
-      sentences = EnumerateGrammarDepth(grammar, length: 20, hashPhrases: false).ToList();
-      Console.WriteLine("Depth: {0} generated, {1} distinct sentences", sentences.Count, sentences.GroupBy(hash).Count());
-
-      sentences = EnumerateGrammarDepth(grammar, length: 20, hashPhrases: true).ToList();
-      Console.WriteLine("Depth (hashed): {0} generated, {1} distinct sentences", sentences.Count, sentences.GroupBy(hash).Count());
-    }
-
+      //var rules = Enum.GetValues(typeof(GrammarRule)).Cast<GrammarRule>().Except(new[] { GrammarRule.InverseTerm, GrammarRule.Exponentiation, GrammarRule.Logarithm, GrammarRule.Sine });
+      var rules = Enum.GetValues(typeof(GrammarRule)).Cast<GrammarRule>();
+      var grammar = new Grammar(variables, rules);
+
+      int maxLength = 20, maxDepth = int.MaxValue;
+      var sentences = EnumerateGrammarDepth(grammar, length: maxLength, depth: maxDepth, hashPhrases: false).ToList();
+      var count = sentences.Count;
+
+      var sw = new Stopwatch();
+      sw.Start();
+      var hashes = sentences.Select(grammar.Hasher.CalcHashCode).ToList();
+      sw.Stop();
+      Console.WriteLine($"Old hash: {sentences.Count} ({hashes.Distinct().Count()}) hashed in {sw.ElapsedMilliseconds / 1000.0} seconds ({1000d * sentences.Count / sw.ElapsedMilliseconds} hashes/s)");
+
+      var ha = SHA512.Create();
+      sw.Restart();
+      var hashes_new = sentences.Select(x => grammar.ComputeHash(ha, x)).ToList();
+      sw.Stop();
+      Console.WriteLine($"New hash: {sentences.Count} ({hashes_new.Distinct().Count()}) hashed in {sw.ElapsedMilliseconds / 1000.0} seconds ({1000.0 * sentences.Count / sw.ElapsedMilliseconds} hashes/s)");
+
+      var distinct = Enumerable.Range(0, count).GroupBy(x => hashes_new[x]).Select(g => g.OrderBy(x => x).First()).ToList();
+      var collisions = distinct.ToLookup(x => hashes[x], x => Tuple.Create(hashes_new[x], sentences[x]));
+
+      foreach (var pair in collisions) {
+        if (pair.Count() > 1) {
+          Console.WriteLine(pair.Key);
+          foreach (var t in pair) {
+            Console.WriteLine($"\t{t}");
+            Console.WriteLine($"\t{grammar.ToInfixString(t.Item2)}");
+            var simplified = grammar.Simplify(ha, t.Item2);
+            Console.WriteLine($"\t{simplified}");
+            Console.Write($"\t");
+            PrintTree(t.Item2);
+            Console.WriteLine();
+          }
+        }
+      }
+    }
+
+    [TestMethod]
+    [TestCategory("TreeHashing")]
+    public void HashPerformance() {
+      var nvars = 4;
+      var variables = Enumerable.Range(0, nvars).Select(x => $"X{x}").ToArray();
+      //var rules = Enum.GetValues(typeof(GrammarRule)).Cast<GrammarRule>().Except(new[] { GrammarRule.InverseTerm, GrammarRule.Exponentiation, GrammarRule.Logarithm, GrammarRule.Sine });
+      var rules = Enum.GetValues(typeof(GrammarRule)).Cast<GrammarRule>();
+      var grammar = new Grammar(variables, rules);
+
+      int maxLength = 20, maxDepth = int.MaxValue;
+      var sentences = EnumerateGrammarDepth(grammar, length: maxLength, depth: maxDepth, hashPhrases: false).ToList();
+      var count = sentences.Count;
+
+      var ha = SHA512.Create();
+
+      var sw = new Stopwatch();
+      sw.Start();
+      var hashes = sentences.Select(x => grammar.ComputeHash(ha, x)).ToList();
+      sw.Stop();
+
+      Console.WriteLine($"New: {sentences.Count} ({hashes.Distinct().Count()}) hashed in {sw.ElapsedMilliseconds / 1000.0} seconds ({1000d * sentences.Count / sw.ElapsedMilliseconds} hashes/s)");
+
+      sw.Restart();
+      var hashes_old = sentences.Select(x => grammar.Hasher.CalcHashCode(x)).ToList();
+      sw.Stop();
+
+      Console.WriteLine($"Old: {sentences.Count} ({hashes_old.Distinct().Count()}) hashed in {sw.ElapsedMilliseconds / 1000.0} seconds ({1000d * sentences.Count / sw.ElapsedMilliseconds} hashes/s)");
+    }
+
+    #region enumerate the grammar
     private static IEnumerable<SymbolList> EnumerateGrammarBreadth(Grammar grammar, int length, bool hashPhrases = true) {
       var phrases = new Queue<SymbolList>();
@@ -201 +347 @@
     }
 
-    private static IEnumerable<SymbolList> EnumerateGrammarDepth(Grammar grammar, int length, bool hashPhrases = true) {
-      return Expand(new SymbolList(grammar.StartSymbol), grammar, length, hashPhrases ? new HashSet<int>() : null);
-    }
-
-    private static IEnumerable<SymbolList> Expand(SymbolList phrase, Grammar grammar, int maxLength, HashSet<int> visited) {
-      if (phrase.Count > maxLength) {
+    private static IEnumerable<SymbolList> EnumerateGrammarDepth(Grammar grammar, int length, int depth, bool hashPhrases = true) {
+      return Expand(new SymbolList(grammar.StartSymbol), grammar, length, 0, depth, hashPhrases ? new HashSet<int>() : null);
+    }
+
+    private static IEnumerable<SymbolList> Expand(SymbolList phrase, Grammar grammar, int maxLength, int depth, int maxDepth, HashSet<int> visited) {
+      if (maxDepth < depth || maxLength < phrase.Count) {
         yield break;
       }
@@ -215 +361 @@
       }
 
-      if (visited != null && !visited.Add(grammar.Hasher.CalcHashCode(phrase))) {
+      if (visited != null && !visited.Add(HashExtensions.ComputeHash(grammar, null, phrase))) {
         yield break;
       }
@@ -222 +368 @@
       var productions = grammar.Productions[phrase[i]];
 
-      foreach (var s in productions.SelectMany(p => Expand(phrase.DerivePhrase(i, p), grammar, maxLength, visited)))
+      foreach (var s in productions.SelectMany(p => Expand(phrase.DerivePhrase(i, p), grammar, maxLength, depth + 1, maxDepth, visited)))
         yield return s;
     }
+    #endregion
   }
 }