Changeset 11486

Timestamp:

10/21/14 19:56:48 (10 years ago)

Author:

bburlacu

Message:

#2215: Renamed BottomUpTreeSimilarityCalculator to BottomUpSimilarityCalculator, improved performance by 10% by using the SymbolicExpressionTreeNodeComparer for ordering nodes (instead of string.Compare on node.ToString()). Updated the rest of the files accordingly.

Location:

branches/HeuristicLab.BottomUpTreeDistance

Files:

• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Analyzers/SymbolicDataAnalysisInternalDiversityAnalyzer.cs (modified) (4 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj (modified) (1 diff)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching/SymbolicExpressionTreeNodeComparer.cs (modified) (2 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs (moved) (moved from branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpTreeSimilarityCalculator.cs) (15 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisProblem.cs (modified) (1 diff)
• HeuristicLab.Tests/BottomUpTreeSimilarityCalculatorTest.cs (modified) (3 diffs)

branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Analyzers/SymbolicDataAnalysisInternalDiversityAnalyzer.cs

@@ -21 +21 @@
 
 using System;
-using System.Collections.Generic;
 using System.Linq;
 using HeuristicLab.Analysis;
@@ -40 +39 @@
     private const string QualityParameterName = "Quality";
     private const string PercentageOfBestSolutionsParameterName = "PercentageOfBestSolutions";
-
     private const string ResultCollectionParameterName = "Results";
-    private readonly BottomUpTreeSimilarityCalculator busCalculator;
+    private readonly BottomUpSimilarityCalculator busCalculator;
 
     public SymbolicDataAnalysisInternalDiversityAnalyzer() {
-      busCalculator = new BottomUpTreeSimilarityCalculator();
+      busCalculator = new BottomUpSimilarityCalculator();
 
       Parameters.Add(new ScopeTreeLookupParameter<ISymbolicExpressionTree>(SymbolicExpressionTreeParameterName));
@@ -103 +101 @@
       var qualities = QualityParameter.ActualValue.ToArray();
 
-      Array.Sort(qualities, trees, new ReverseComparer());
+      var pairs = trees.Zip(qualities, (t, q) => new { Tree = t, Quality = q }).OrderByDescending(x => x.Quality);
       int n = (int)Math.Floor(trees.Length * PercentageOfBestSolutions);
-
-      double avgInternalDiversity = trees.Take(n).Average(tree => CalculateInternalDiversity(tree));
+      double avgInternalDiversity = pairs.Take(n).Average(x => CalculateInternalDiversity(x.Tree));
 
       table.Rows["Avg. Internal Diversity"].Values.Add(avgInternalDiversity);
@@ -136 +133 @@
     }
   }
-
-  internal class ReverseComparer : IComparer<DoubleValue> {
-    public int Compare(DoubleValue x, DoubleValue y) {
-      return y.CompareTo(x);
-    }
-  }
 }

branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj

@@ -219 +219 @@
     <Compile Include="Matching\SymbolicExpressionTreeNodeComparer.cs" />
     <Compile Include="Matching\SymbolicExpressionTreeNodeSimilarityComparer.cs" />
-    <Compile Include="SimilarityCalculators\BottomUpTreeSimilarityCalculator.cs" />
+    <Compile Include="SimilarityCalculators\BottomUpSimilarityCalculator.cs" />
     <Compile Include="SimilarityCalculators\MaxCommonSubtreeSimilarityCalculator.cs" />
     <Compile Include="SymbolicExpressionTreeBacktransformator.cs" />

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

@@ -1 @@
-using System;
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2014 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ *
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using System;
 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 
@@ -9 +30 @@
   public class SymbolicExpressionTreeNodeComparer : ISymbolicExpressionTreeNodeComparer {
     public int Compare(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
-      if (!(a is SymbolicExpressionTreeTerminalNode)) {
-        return b is SymbolicExpressionTreeTerminalNode
-          ? -1
-          : string.Compare(a.Symbol.Name, b.Symbol.Name, StringComparison.Ordinal);
-      }
-      if (!(b is SymbolicExpressionTreeTerminalNode)) return 1;
-      // at this point we know a and b are terminal nodes
+      var ta = a as SymbolicExpressionTreeTerminalNode;
+      var tb = b as SymbolicExpressionTreeTerminalNode;
+
+      if (ta == null)
+        return tb == null ? String.CompareOrdinal(a.Symbol.Name, b.Symbol.Name) : -1;
+
+      if (tb == null)
+        return 1;
+
+      // at this point we know a and b are both terminals
       var va = a as VariableTreeNode;
-      if (va != null) {
-        if (b is ConstantTreeNode) return -1;
-        var vb = (VariableTreeNode)b;
-        return (va.VariableName.Equals(vb.VariableName)
-          ? va.Weight.CompareTo(vb.Weight)
-          : string.Compare(va.VariableName, vb.VariableName, StringComparison.Ordinal));
-      }
-      // at this point we know for sure that a is a constant tree node
-      if (b is VariableTreeNode) return 1;
-      var ca = (ConstantTreeNode)a;
-      var cb = (ConstantTreeNode)b;
-      return ca.Value.CompareTo(cb.Value);
+      var vb = b as VariableTreeNode;
+
+      if (va != null)
+        return vb == null ? -1 : CompareVariables(va, vb);
+
+      if (vb != null)
+        return 1;
+
+      // at this point we know a and b are not variables
+      var ca = a as ConstantTreeNode;
+      var cb = b as ConstantTreeNode;
+
+      if (ca != null && cb != null)
+        return ca.Value.CompareTo(cb.Value);
+
+      // for other unknown terminal types, compare strings
+      return string.CompareOrdinal(a.ToString(), b.ToString());
+    }
+
+    private static int CompareVariables(VariableTreeNode a, VariableTreeNode b) {
+      int result = string.CompareOrdinal(a.VariableName, b.VariableName);
+      return result == 0 ? a.Weight.CompareTo(b.Weight) : result;
     }
   }
+
 }

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

@@ -22 +22 @@
 using System;
 using System.Collections.Generic;
+using System.Diagnostics;
+using System.Globalization;
 using System.Linq;
 using HeuristicLab.Common;
@@ -31 +33 @@
 namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
   [StorableClass]
-  [Item("BottomUpTreeSimilarityCalculator", "A similarity calculator which uses the tree bottom-up distance as a similarity metric.")]
-  public class BottomUpTreeSimilarityCalculator : SingleObjectiveSolutionSimilarityCalculator {
-    private readonly HashSet<string> commutativeSymbols;
-
-    public BottomUpTreeSimilarityCalculator() {
-      commutativeSymbols = new HashSet<string>();
-    }
-
-    public BottomUpTreeSimilarityCalculator(IEnumerable<string> commutativeSymbols) {
-      this.commutativeSymbols = new HashSet<string>(commutativeSymbols);
+  [Item("BottomUpSimilarityCalculator", "A similarity calculator which uses the tree bottom-up distance as a similarity metric.")]
+  public class BottomUpSimilarityCalculator : SingleObjectiveSolutionSimilarityCalculator {
+    private readonly HashSet<string> commutativeSymbols = new HashSet<string> { "Addition", "Multiplication", "Average", "And", "Or", "Xor" };
+    public bool MatchVariableWeights { get; set; }
+    public bool MatchConstantValues { get; set; }
+
+    public BottomUpSimilarityCalculator() { }
+
+    protected BottomUpSimilarityCalculator(BottomUpSimilarityCalculator original, Cloner cloner)
+      : base(original, cloner) {
     }
 
     public override IDeepCloneable Clone(Cloner cloner) {
-      return new BottomUpTreeSimilarityCalculator(this, cloner);
-    }
-
-    protected BottomUpTreeSimilarityCalculator(BottomUpTreeSimilarityCalculator original, Cloner cloner)
-      : base(original, cloner) {
+      return new BottomUpSimilarityCalculator(this, cloner);
+    }
+
+    public double CalculateSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
+      if (t1 == t2)
+        return 1;
+
+      var map = ComputeBottomUpMapping(t1.Root, t2.Root);
+      return 2.0 * map.Count / (t1.Length + t2.Length);
     }
 
@@ -58 +64 @@
         throw new ArgumentException("Cannot calculate similarity when one of the arguments is null.");
 
-      var similarity = CalculateSolutionSimilarity(t1, t2);
+      var similarity = CalculateSimilarity(t1, t2);
       if (similarity > 1.0)
         throw new Exception("Similarity value cannot be greater than 1");
@@ -65 +71 @@
     }
 
-    public bool AddCommutativeSymbol(string symbolName) {
-      return commutativeSymbols.Add(symbolName);
-    }
-
-    public bool RemoveCommutativeSymbol(string symbolName) {
-      return commutativeSymbols.Remove(symbolName);
-    }
-
-    public double CalculateSolutionSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
-      if (t1 == t2)
-        return 1;
-
-      var map = ComputeBottomUpMapping(t1.Root, t2.Root);
-      return 2.0 * map.Count / (t1.Length + t2.Length);
-    }
-
     public Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> ComputeBottomUpMapping(ISymbolicExpressionTreeNode n1, ISymbolicExpressionTreeNode n2) {
+      var comparer = new SymbolicExpressionTreeNodeComparer(); // use a node comparer because it's faster than calling node.ToString() (strings are expensive) and comparing strings
       var compactedGraph = Compact(n1, n2);
 
@@ -103 +94 @@
         // 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).GetEnumerator();
-        var eW = IterateBreadthOrdered(w).GetEnumerator();
+        var eV = IterateBreadthOrdered(v, comparer).GetEnumerator();
+        var eW = IterateBreadthOrdered(w, comparer).GetEnumerator();
 
         while (eV.MoveNext() && eW.MoveNext()) {
@@ -110 +101 @@
           var t = eW.Current;
 
-          if (reverseMap.ContainsKey(t)) {
-            throw new Exception("A mapping to this node already exists.");
-          }
+          Debug.Assert(!reverseMap.ContainsKey(t));
 
           forwardMap[s] = t;
@@ -134 +123 @@
 
       var nodes = n1.IterateNodesPostfix().Concat(n2.IterateNodesPostfix()); // the disjoint union F
-      var list = new List<GraphNode>();
+      var list = new List<GraphNode>(); // preallocate size to avoid list resizing as it has a performance hit
       var queue = new Queue<ISymbolicExpressionTreeNode>();
 
       foreach (var n in nodes) {
         if (n.SubtreeCount == 0) {
-          var label = n.ToString();
+          var label = Label(n);
           if (!labelMap.ContainsKey(label)) {
             var z = new GraphNode { SymbolicExpressionTreeNode = n, Label = label };
@@ -161 +150 @@
           bool sort = commutativeSymbols.Contains(label);
           var nNodes = n.Subtrees.Select(x => nodeMap[x]).ToList();
-          if (sort) nNodes.Sort((a, b) => String.Compare(a.Label, b.Label, StringComparison.Ordinal));
+          if (sort) nNodes.Sort((a, b) => string.CompareOrdinal(a.Label, b.Label));
 
           for (int i = list.Count - 1; i >= 0; --i) {
@@ -172 +161 @@
             var m = w.SymbolicExpressionTreeNode;
             var mNodes = m.Subtrees.Select(x => nodeMap[x]).ToList();
-            if (sort) mNodes.Sort((a, b) => String.Compare(a.Label, b.Label, StringComparison.Ordinal));
+            if (sort) mNodes.Sort((a, b) => string.CompareOrdinal(a.Label, b.Label));
 
             if (nNodes.SequenceEqual(mNodes)) {
@@ -182 +171 @@
 
           if (!found) {
-            var w = new GraphNode { SymbolicExpressionTreeNode = n, Label = label, Depth = depth, ChildrenCount = n.SubtreeCount };
+            var w = new GraphNode { SymbolicExpressionTreeNode = n, Label = label, Depth = depth };
             list.Add(w);
             nodeMap[n] = w;
@@ -188 +177 @@
         }
 
+        if (n == n1 || n == n2)
+          continue;
+
         var p = n.Parent;
         if (p == null)
@@ -201 +193 @@
     }
 
-    /// <summary>
-    /// This method iterates the nodes of a subtree in breadth order while also sorting the subtrees of commutative symbols based on their label.
-    /// This is necessary in order for the mapping to be realized correctly.
-    /// </summary>
-    /// <param name="node">The root of the subtree</param>
-    /// <returns>A list of nodes in breadth order (with children of commutative symbols sorted by label)</returns>
-    private IEnumerable<ISymbolicExpressionTreeNode> IterateBreadthOrdered(ISymbolicExpressionTreeNode node) {
+    private IEnumerable<ISymbolicExpressionTreeNode> IterateBreadthOrdered(ISymbolicExpressionTreeNode node, ISymbolicExpressionTreeNodeComparer comparer) {
       var list = new List<ISymbolicExpressionTreeNode> { node };
       int i = 0;
@@ -213 +199 @@
         var n = list[i];
         if (n.SubtreeCount > 0) {
-          var subtrees = commutativeSymbols.Contains(node.Symbol.Name) ? n.Subtrees.OrderBy(x => x.ToString(), StringComparer.Ordinal) : n.Subtrees;
+          var subtrees = commutativeSymbols.Contains(node.Symbol.Name) ? n.Subtrees.OrderBy(x => x, comparer) : n.Subtrees;
           list.AddRange(subtrees);
         }
@@ -219 +205 @@
       }
       return list;
+    }
+
+    private string Label(ISymbolicExpressionTreeNode node) {
+      if (node.SubtreeCount > 0)
+        return node.Symbol.Name;
+
+      var constant = node as ConstantTreeNode;
+      if (constant != null)
+        return MatchConstantValues ? constant.Value.ToString(CultureInfo.InvariantCulture) : constant.Symbol.Name;
+      var variable = node as VariableTreeNode;
+      if (variable != null) {
+        return MatchVariableWeights ? variable.Weight + variable.VariableName : variable.VariableName;
+      }
+
+      return node.ToString();
     }
 
@@ -225 +226 @@
       public string Label;
       public int Depth;
-      public int ChildrenCount;
+      public int ChildrenCount { get { return SymbolicExpressionTreeNode.SubtreeCount; } }
     }
   }

branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisProblem.cs

@@ -358 +358 @@
       }
       foreach (var op in operators.OfType<SingleObjectivePopulationDiversityAnalyzer>()) {
-        op.SimilarityCalculator = new BottomUpTreeSimilarityCalculator();
+        op.SimilarityCalculator = new BottomUpSimilarityCalculator();
       }
     }

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

@@ -14 +14 @@
   [TestClass]
   public class BottomUpSimilarityCalculatorTest {
-    private readonly BottomUpTreeSimilarityCalculator busCalculator;
+    private readonly BottomUpSimilarityCalculator busCalculator;
     private readonly SymbolicExpressionImporter importer;
 
@@ -22 +22 @@
 
     public BottomUpSimilarityCalculatorTest() {
-      busCalculator = new BottomUpTreeSimilarityCalculator(new List<string> { "Addition", "Multiplication", "And", "Or", "Xor" });
+      busCalculator = new BottomUpSimilarityCalculator { MatchConstantValues = true, MatchVariableWeights = true };
       importer = new SymbolicExpressionImporter();
     }
@@ -85 +85 @@
       for (int i = 0; i < trees.Length - 1; ++i) {
         for (int j = i + 1; j < trees.Length; ++j) {
-          s += busCalculator.CalculateSolutionSimilarity(trees[i], trees[j]);
+          s += busCalculator.CalculateSimilarity(trees[i], trees[j]);
         }
       }