Changeset 11894

Timestamp:

02/04/15 23:55:42 (9 years ago)

Author:

bburlacu

Message:

#2215: Performance optimizations (up to 25% faster).

Location:

branches/HeuristicLab.BottomUpTreeDistance

Files:

• HeuristicLab.BottomUpTreeDistance.sln (modified) (2 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching/SymbolicExpressionTreeNodeComparer.cs (modified) (3 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs (modified) (5 diffs)
• HeuristicLab.Tests/BottomUpTreeSimilarityCalculatorTest.cs (modified) (1 diff)

branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.BottomUpTreeDistance.sln

@@ -2 +2 @@
 Microsoft Visual Studio Solution File, Format Version 12.00
 # Visual Studio 2013
-VisualStudioVersion = 12.0.30501.0
+VisualStudioVersion = 12.0.31101.0
 MinimumVisualStudioVersion = 10.0.40219.1
 Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.DataAnalysis.Symbolic-3.4", "HeuristicLab.Problems.DataAnalysis.Symbolic\3.4\HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj", "{3D28463F-EC96-4D82-AFEE-38BE91A0CA00}"
@@ -36 +36 @@
     {07C05C8F-0769-4607-96C6-D90A219F4C85}.Release|Any CPU.ActiveCfg = Release|Any CPU
     {07C05C8F-0769-4607-96C6-D90A219F4C85}.Release|Any CPU.Build.0 = Release|Any CPU
-    {07C05C8F-0769-4607-96C6-D90A219F4C85}.Release|x64.ActiveCfg = Release|Any CPU
-    {07C05C8F-0769-4607-96C6-D90A219F4C85}.Release|x86.ActiveCfg = Release|Any CPU
+    {07C05C8F-0769-4607-96C6-D90A219F4C85}.Release|x64.ActiveCfg = Release|x64
+    {07C05C8F-0769-4607-96C6-D90A219F4C85}.Release|x64.Build.0 = Release|x64
+    {07C05C8F-0769-4607-96C6-D90A219F4C85}.Release|x86.ActiveCfg = Release|x86
+    {07C05C8F-0769-4607-96C6-D90A219F4C85}.Release|x86.Build.0 = Release|x86
   EndGlobalSection
   GlobalSection(SolutionProperties) = preSolution

branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching/SymbolicExpressionTreeNodeComparer.cs

@@ -21 +21 @@
 
 using System;
+using System.Collections.Generic;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 
@@ -29 +30 @@
   // - used for bringing subtrees to a "canonical" form when the operation allows reordering of arguments
   public class SymbolicExpressionTreeNodeComparer : ISymbolicExpressionTreeNodeComparer {
-    public int Compare(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
+    public static int Compare(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
       var ta = a as SymbolicExpressionTreeTerminalNode;
       var tb = b as SymbolicExpressionTreeTerminalNode;
@@ -64 +65 @@
       return result == 0 ? a.Weight.CompareTo(b.Weight) : result;
     }
+
+    int IComparer<ISymbolicExpressionTreeNode>.Compare(ISymbolicExpressionTreeNode x, ISymbolicExpressionTreeNode y) {
+      return Compare(x, y);
+    }
   }
 

branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs

@@ -83 +83 @@
       var nodes1 = n1.IterateNodesPrefix().ToList();
       var nodes2 = n2.IterateNodesPrefix().ToList();
-      foreach (var v in nodes1) {
+      for (int i = 0; i < nodes1.Count; ++i) {
+        var v = nodes1[i];
         if (forwardMap.ContainsKey(v))
           continue;
         var kv = compactedGraph[v];
         ISymbolicExpressionTreeNode w = null;
-        foreach (var t in nodes2) {
+        for (int j = 0; j < nodes2.Count; ++j) {
+          var t = nodes2[j];
           if (reverseMap.ContainsKey(t) || compactedGraph[t] != kv)
             continue;
@@ -98 +100 @@
         // at this point we know that v and w are isomorphic, however, the mapping cannot be done directly (as in the paper) because the trees are unordered (subtree order might differ)
         // the solution is to sort subtrees by label using IterateBreadthOrdered (this will work because the subtrees are isomorphic!) and simultaneously iterate over the two subtrees
-        var eV = IterateBreadthOrdered(v, comparer).GetEnumerator();
-        var eW = IterateBreadthOrdered(w, comparer).GetEnumerator();
-
-        while (eV.MoveNext() && eW.MoveNext()) {
-          var s = eV.Current;
-          var t = eW.Current;
-
+        var vv = IterateBreadthOrdered(v, comparer).ToList();
+        var ww = IterateBreadthOrdered(w, comparer).ToList();
+        int len = Math.Min(vv.Count, ww.Count);
+        for (int j = 0; j < len; ++j) {
+          var s = vv[j];
+          var t = ww[j];
           Debug.Assert(!reverseMap.ContainsKey(t));
 
@@ -136 +137 @@
             var z = new GraphNode { SymbolicExpressionTreeNode = n, Label = label };
             labelMap[z.Label] = z;
-            list.Add(z);
           }
           nodeMap[n] = labelMap[label];
@@ -146 +146 @@
       while (queue.Any()) {
         var n = queue.Dequeue();
-
         if (n.SubtreeCount > 0) {
+          bool found = false;
           var label = n.Symbol.Name;
-          bool found = false;
           var depth = n.GetDepth();
 
-          bool sort = commutativeSymbols.Contains(label);
-          var nNodes = n.Subtrees.Select(x => nodeMap[x]).ToList();
-          if (sort) nNodes.Sort((a, b) => string.CompareOrdinal(a.Label, b.Label));
+          bool sort = n.SubtreeCount > 1 && commutativeSymbols.Contains(label);
+          var nSubtrees = n.Subtrees.Select(x => nodeMap[x]).ToList();
+          if (sort) nSubtrees.Sort((a, b) => string.CompareOrdinal(a.Label, b.Label));
 
           for (int i = list.Count - 1; i >= 0; --i) {
             var w = list[i];
-
-            if (!(n.SubtreeCount == w.ChildrenCount && label == w.Label && depth == w.Depth))
+            if (!(n.SubtreeCount == w.SubtreeCount && label == w.Label && depth == w.Depth))
               continue;
 
             // sort V and W when the symbol is commutative because we are dealing with unordered trees
             var m = w.SymbolicExpressionTreeNode;
-            var mNodes = m.Subtrees.Select(x => nodeMap[x]).ToList();
-            if (sort) mNodes.Sort((a, b) => string.CompareOrdinal(a.Label, b.Label));
-
-            if (nNodes.SequenceEqual(mNodes)) {
+            var mSubtrees = m.Subtrees.Select(x => nodeMap[x]).ToList();
+            if (sort) mSubtrees.Sort((a, b) => string.CompareOrdinal(a.Label, b.Label));
+
+            found = nSubtrees.SequenceEqual(mSubtrees);
+            if (found) {
               nodeMap[n] = w;
-              found = true;
               break;
             }
@@ -230 +228 @@
       public string Label;
       public int Depth;
-      public int ChildrenCount { get { return SymbolicExpressionTreeNode.SubtreeCount; } }
+      public int SubtreeCount { get { return SymbolicExpressionTreeNode.SubtreeCount; } }
     }
   }

branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Tests/BottomUpTreeSimilarityCalculatorTest.cs

@@ -17 +17 @@
     private readonly SymbolicExpressionImporter importer;
 
-    private const int N = 100;
+    private const int N = 150;
     private const int Rows = 1;
     private const int Columns = 10;