Free cookie consent management tool by TermsFeed Policy Generator

Changeset 11486


Ignore:
Timestamp:
10/21/14 19:56:48 (8 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:
5 edited
1 moved

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Analyzers/SymbolicDataAnalysisInternalDiversityAnalyzer.cs

    r11239 r11486  
    2121
    2222using System;
    23 using System.Collections.Generic;
    2423using System.Linq;
    2524using HeuristicLab.Analysis;
     
    4039    private const string QualityParameterName = "Quality";
    4140    private const string PercentageOfBestSolutionsParameterName = "PercentageOfBestSolutions";
    42 
    4341    private const string ResultCollectionParameterName = "Results";
    44     private readonly BottomUpTreeSimilarityCalculator busCalculator;
     42    private readonly BottomUpSimilarityCalculator busCalculator;
    4543
    4644    public SymbolicDataAnalysisInternalDiversityAnalyzer() {
    47       busCalculator = new BottomUpTreeSimilarityCalculator();
     45      busCalculator = new BottomUpSimilarityCalculator();
    4846
    4947      Parameters.Add(new ScopeTreeLookupParameter<ISymbolicExpressionTree>(SymbolicExpressionTreeParameterName));
     
    103101      var qualities = QualityParameter.ActualValue.ToArray();
    104102
    105       Array.Sort(qualities, trees, new ReverseComparer());
     103      var pairs = trees.Zip(qualities, (t, q) => new { Tree = t, Quality = q }).OrderByDescending(x => x.Quality);
    106104      int n = (int)Math.Floor(trees.Length * PercentageOfBestSolutions);
    107 
    108       double avgInternalDiversity = trees.Take(n).Average(tree => CalculateInternalDiversity(tree));
     105      double avgInternalDiversity = pairs.Take(n).Average(x => CalculateInternalDiversity(x.Tree));
    109106
    110107      table.Rows["Avg. Internal Diversity"].Values.Add(avgInternalDiversity);
     
    136133    }
    137134  }
    138 
    139   internal class ReverseComparer : IComparer<DoubleValue> {
    140     public int Compare(DoubleValue x, DoubleValue y) {
    141       return y.CompareTo(x);
    142     }
    143   }
    144135}
  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj

    r11243 r11486  
    219219    <Compile Include="Matching\SymbolicExpressionTreeNodeComparer.cs" />
    220220    <Compile Include="Matching\SymbolicExpressionTreeNodeSimilarityComparer.cs" />
    221     <Compile Include="SimilarityCalculators\BottomUpTreeSimilarityCalculator.cs" />
     221    <Compile Include="SimilarityCalculators\BottomUpSimilarityCalculator.cs" />
    222222    <Compile Include="SimilarityCalculators\MaxCommonSubtreeSimilarityCalculator.cs" />
    223223    <Compile Include="SymbolicExpressionTreeBacktransformator.cs" />
  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching/SymbolicExpressionTreeNodeComparer.cs

    r10562 r11486  
    1 using System;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2014 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     4 *
     5 * This file is part of HeuristicLab.
     6 *
     7 * HeuristicLab is free software: you can redistribute it and/or modify
     8 * it under the terms of the GNU General Public License as published by
     9 * the Free Software Foundation, either version 3 of the License, or
     10 * (at your option) any later version.
     11 *
     12 * HeuristicLab is distributed in the hope that it will be useful,
     13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
     14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     15 * GNU General Public License for more details.
     16 *
     17 * You should have received a copy of the GNU General Public License
     18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
     19 */
     20#endregion
     21
     22using System;
    223using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    324
     
    930  public class SymbolicExpressionTreeNodeComparer : ISymbolicExpressionTreeNodeComparer {
    1031    public int Compare(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
    11       if (!(a is SymbolicExpressionTreeTerminalNode)) {
    12         return b is SymbolicExpressionTreeTerminalNode
    13           ? -1
    14           : string.Compare(a.Symbol.Name, b.Symbol.Name, StringComparison.Ordinal);
    15       }
    16       if (!(b is SymbolicExpressionTreeTerminalNode)) return 1;
    17       // at this point we know a and b are terminal nodes
     32      var ta = a as SymbolicExpressionTreeTerminalNode;
     33      var tb = b as SymbolicExpressionTreeTerminalNode;
     34
     35      if (ta == null)
     36        return tb == null ? String.CompareOrdinal(a.Symbol.Name, b.Symbol.Name) : -1;
     37
     38      if (tb == null)
     39        return 1;
     40
     41      // at this point we know a and b are both terminals
    1842      var va = a as VariableTreeNode;
    19       if (va != null) {
    20         if (b is ConstantTreeNode) return -1;
    21         var vb = (VariableTreeNode)b;
    22         return (va.VariableName.Equals(vb.VariableName)
    23           ? va.Weight.CompareTo(vb.Weight)
    24           : string.Compare(va.VariableName, vb.VariableName, StringComparison.Ordinal));
    25       }
    26       // at this point we know for sure that a is a constant tree node
    27       if (b is VariableTreeNode) return 1;
    28       var ca = (ConstantTreeNode)a;
    29       var cb = (ConstantTreeNode)b;
    30       return ca.Value.CompareTo(cb.Value);
     43      var vb = b as VariableTreeNode;
     44
     45      if (va != null)
     46        return vb == null ? -1 : CompareVariables(va, vb);
     47
     48      if (vb != null)
     49        return 1;
     50
     51      // at this point we know a and b are not variables
     52      var ca = a as ConstantTreeNode;
     53      var cb = b as ConstantTreeNode;
     54
     55      if (ca != null && cb != null)
     56        return ca.Value.CompareTo(cb.Value);
     57
     58      // for other unknown terminal types, compare strings
     59      return string.CompareOrdinal(a.ToString(), b.ToString());
     60    }
     61
     62    private static int CompareVariables(VariableTreeNode a, VariableTreeNode b) {
     63      int result = string.CompareOrdinal(a.VariableName, b.VariableName);
     64      return result == 0 ? a.Weight.CompareTo(b.Weight) : result;
    3165    }
    3266  }
     67
    3368}
  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs

    r11482 r11486  
    2222using System;
    2323using System.Collections.Generic;
     24using System.Diagnostics;
     25using System.Globalization;
    2426using System.Linq;
    2527using HeuristicLab.Common;
     
    3133namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
    3234  [StorableClass]
    33   [Item("BottomUpTreeSimilarityCalculator", "A similarity calculator which uses the tree bottom-up distance as a similarity metric.")]
    34   public class BottomUpTreeSimilarityCalculator : SingleObjectiveSolutionSimilarityCalculator {
    35     private readonly HashSet<string> commutativeSymbols;
    36 
    37     public BottomUpTreeSimilarityCalculator() {
    38       commutativeSymbols = new HashSet<string>();
    39     }
    40 
    41     public BottomUpTreeSimilarityCalculator(IEnumerable<string> commutativeSymbols) {
    42       this.commutativeSymbols = new HashSet<string>(commutativeSymbols);
     35  [Item("BottomUpSimilarityCalculator", "A similarity calculator which uses the tree bottom-up distance as a similarity metric.")]
     36  public class BottomUpSimilarityCalculator : SingleObjectiveSolutionSimilarityCalculator {
     37    private readonly HashSet<string> commutativeSymbols = new HashSet<string> { "Addition", "Multiplication", "Average", "And", "Or", "Xor" };
     38    public bool MatchVariableWeights { get; set; }
     39    public bool MatchConstantValues { get; set; }
     40
     41    public BottomUpSimilarityCalculator() { }
     42
     43    protected BottomUpSimilarityCalculator(BottomUpSimilarityCalculator original, Cloner cloner)
     44      : base(original, cloner) {
    4345    }
    4446
    4547    public override IDeepCloneable Clone(Cloner cloner) {
    46       return new BottomUpTreeSimilarityCalculator(this, cloner);
    47     }
    48 
    49     protected BottomUpTreeSimilarityCalculator(BottomUpTreeSimilarityCalculator original, Cloner cloner)
    50       : base(original, cloner) {
     48      return new BottomUpSimilarityCalculator(this, cloner);
     49    }
     50
     51    public double CalculateSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
     52      if (t1 == t2)
     53        return 1;
     54
     55      var map = ComputeBottomUpMapping(t1.Root, t2.Root);
     56      return 2.0 * map.Count / (t1.Length + t2.Length);
    5157    }
    5258
     
    5864        throw new ArgumentException("Cannot calculate similarity when one of the arguments is null.");
    5965
    60       var similarity = CalculateSolutionSimilarity(t1, t2);
     66      var similarity = CalculateSimilarity(t1, t2);
    6167      if (similarity > 1.0)
    6268        throw new Exception("Similarity value cannot be greater than 1");
     
    6571    }
    6672
    67     public bool AddCommutativeSymbol(string symbolName) {
    68       return commutativeSymbols.Add(symbolName);
    69     }
    70 
    71     public bool RemoveCommutativeSymbol(string symbolName) {
    72       return commutativeSymbols.Remove(symbolName);
    73     }
    74 
    75     public double CalculateSolutionSimilarity(ISymbolicExpressionTree t1, ISymbolicExpressionTree t2) {
    76       if (t1 == t2)
    77         return 1;
    78 
    79       var map = ComputeBottomUpMapping(t1.Root, t2.Root);
    80       return 2.0 * map.Count / (t1.Length + t2.Length);
    81     }
    82 
    8373    public Dictionary<ISymbolicExpressionTreeNode, ISymbolicExpressionTreeNode> ComputeBottomUpMapping(ISymbolicExpressionTreeNode n1, ISymbolicExpressionTreeNode n2) {
     74      var comparer = new SymbolicExpressionTreeNodeComparer(); // use a node comparer because it's faster than calling node.ToString() (strings are expensive) and comparing strings
    8475      var compactedGraph = Compact(n1, n2);
    8576
     
    10394        // 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)
    10495        // 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
    105         var eV = IterateBreadthOrdered(v).GetEnumerator();
    106         var eW = IterateBreadthOrdered(w).GetEnumerator();
     96        var eV = IterateBreadthOrdered(v, comparer).GetEnumerator();
     97        var eW = IterateBreadthOrdered(w, comparer).GetEnumerator();
    10798
    10899        while (eV.MoveNext() && eW.MoveNext()) {
     
    110101          var t = eW.Current;
    111102
    112           if (reverseMap.ContainsKey(t)) {
    113             throw new Exception("A mapping to this node already exists.");
    114           }
     103          Debug.Assert(!reverseMap.ContainsKey(t));
    115104
    116105          forwardMap[s] = t;
     
    134123
    135124      var nodes = n1.IterateNodesPostfix().Concat(n2.IterateNodesPostfix()); // the disjoint union F
    136       var list = new List<GraphNode>();
     125      var list = new List<GraphNode>(); // preallocate size to avoid list resizing as it has a performance hit
    137126      var queue = new Queue<ISymbolicExpressionTreeNode>();
    138127
    139128      foreach (var n in nodes) {
    140129        if (n.SubtreeCount == 0) {
    141           var label = n.ToString();
     130          var label = Label(n);
    142131          if (!labelMap.ContainsKey(label)) {
    143132            var z = new GraphNode { SymbolicExpressionTreeNode = n, Label = label };
     
    161150          bool sort = commutativeSymbols.Contains(label);
    162151          var nNodes = n.Subtrees.Select(x => nodeMap[x]).ToList();
    163           if (sort) nNodes.Sort((a, b) => String.Compare(a.Label, b.Label, StringComparison.Ordinal));
     152          if (sort) nNodes.Sort((a, b) => string.CompareOrdinal(a.Label, b.Label));
    164153
    165154          for (int i = list.Count - 1; i >= 0; --i) {
     
    172161            var m = w.SymbolicExpressionTreeNode;
    173162            var mNodes = m.Subtrees.Select(x => nodeMap[x]).ToList();
    174             if (sort) mNodes.Sort((a, b) => String.Compare(a.Label, b.Label, StringComparison.Ordinal));
     163            if (sort) mNodes.Sort((a, b) => string.CompareOrdinal(a.Label, b.Label));
    175164
    176165            if (nNodes.SequenceEqual(mNodes)) {
     
    182171
    183172          if (!found) {
    184             var w = new GraphNode { SymbolicExpressionTreeNode = n, Label = label, Depth = depth, ChildrenCount = n.SubtreeCount };
     173            var w = new GraphNode { SymbolicExpressionTreeNode = n, Label = label, Depth = depth };
    185174            list.Add(w);
    186175            nodeMap[n] = w;
     
    188177        }
    189178
     179        if (n == n1 || n == n2)
     180          continue;
     181
    190182        var p = n.Parent;
    191183        if (p == null)
     
    201193    }
    202194
    203     /// <summary>
    204     /// This method iterates the nodes of a subtree in breadth order while also sorting the subtrees of commutative symbols based on their label.
    205     /// This is necessary in order for the mapping to be realized correctly.
    206     /// </summary>
    207     /// <param name="node">The root of the subtree</param>
    208     /// <returns>A list of nodes in breadth order (with children of commutative symbols sorted by label)</returns>
    209     private IEnumerable<ISymbolicExpressionTreeNode> IterateBreadthOrdered(ISymbolicExpressionTreeNode node) {
     195    private IEnumerable<ISymbolicExpressionTreeNode> IterateBreadthOrdered(ISymbolicExpressionTreeNode node, ISymbolicExpressionTreeNodeComparer comparer) {
    210196      var list = new List<ISymbolicExpressionTreeNode> { node };
    211197      int i = 0;
     
    213199        var n = list[i];
    214200        if (n.SubtreeCount > 0) {
    215           var subtrees = commutativeSymbols.Contains(node.Symbol.Name) ? n.Subtrees.OrderBy(x => x.ToString(), StringComparer.Ordinal) : n.Subtrees;
     201          var subtrees = commutativeSymbols.Contains(node.Symbol.Name) ? n.Subtrees.OrderBy(x => x, comparer) : n.Subtrees;
    216202          list.AddRange(subtrees);
    217203        }
     
    219205      }
    220206      return list;
     207    }
     208
     209    private string Label(ISymbolicExpressionTreeNode node) {
     210      if (node.SubtreeCount > 0)
     211        return node.Symbol.Name;
     212
     213      var constant = node as ConstantTreeNode;
     214      if (constant != null)
     215        return MatchConstantValues ? constant.Value.ToString(CultureInfo.InvariantCulture) : constant.Symbol.Name;
     216      var variable = node as VariableTreeNode;
     217      if (variable != null) {
     218        return MatchVariableWeights ? variable.Weight + variable.VariableName : variable.VariableName;
     219      }
     220
     221      return node.ToString();
    221222    }
    222223
     
    225226      public string Label;
    226227      public int Depth;
    227       public int ChildrenCount;
     228      public int ChildrenCount { get { return SymbolicExpressionTreeNode.SubtreeCount; } }
    228229    }
    229230  }
  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SymbolicDataAnalysisProblem.cs

    r11254 r11486  
    358358      }
    359359      foreach (var op in operators.OfType<SingleObjectivePopulationDiversityAnalyzer>()) {
    360         op.SimilarityCalculator = new BottomUpTreeSimilarityCalculator();
     360        op.SimilarityCalculator = new BottomUpSimilarityCalculator();
    361361      }
    362362    }
  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Tests/BottomUpTreeSimilarityCalculatorTest.cs

    r11244 r11486  
    1414  [TestClass]
    1515  public class BottomUpSimilarityCalculatorTest {
    16     private readonly BottomUpTreeSimilarityCalculator busCalculator;
     16    private readonly BottomUpSimilarityCalculator busCalculator;
    1717    private readonly SymbolicExpressionImporter importer;
    1818
     
    2222
    2323    public BottomUpSimilarityCalculatorTest() {
    24       busCalculator = new BottomUpTreeSimilarityCalculator(new List<string> { "Addition", "Multiplication", "And", "Or", "Xor" });
     24      busCalculator = new BottomUpSimilarityCalculator { MatchConstantValues = true, MatchVariableWeights = true };
    2525      importer = new SymbolicExpressionImporter();
    2626    }
     
    8585      for (int i = 0; i < trees.Length - 1; ++i) {
    8686        for (int j = i + 1; j < trees.Length; ++j) {
    87           s += busCalculator.CalculateSolutionSimilarity(trees[i], trees[j]);
     87          s += busCalculator.CalculateSimilarity(trees[i], trees[j]);
    8888        }
    8989      }
Note: See TracChangeset for help on using the changeset viewer.