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

Timestamp:

10/21/14 19:56:48 (9 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.

File:

• branches/HeuristicLab.BottomUpTreeDistance/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)

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; } }
     }
   }