Free cookie consent management tool by TermsFeed Policy Generator

Changeset 11894 for branches


Ignore:
Timestamp:
02/04/15 23:55:42 (10 years ago)
Author:
bburlacu
Message:

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

Location:
branches/HeuristicLab.BottomUpTreeDistance
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.BottomUpTreeDistance.sln

    r11234 r11894  
    22Microsoft Visual Studio Solution File, Format Version 12.00
    33# Visual Studio 2013
    4 VisualStudioVersion = 12.0.30501.0
     4VisualStudioVersion = 12.0.31101.0
    55MinimumVisualStudioVersion = 10.0.40219.1
    66Project("{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}"
     
    3636    {07C05C8F-0769-4607-96C6-D90A219F4C85}.Release|Any CPU.ActiveCfg = Release|Any CPU
    3737    {07C05C8F-0769-4607-96C6-D90A219F4C85}.Release|Any CPU.Build.0 = Release|Any CPU
    38     {07C05C8F-0769-4607-96C6-D90A219F4C85}.Release|x64.ActiveCfg = Release|Any CPU
    39     {07C05C8F-0769-4607-96C6-D90A219F4C85}.Release|x86.ActiveCfg = Release|Any CPU
     38    {07C05C8F-0769-4607-96C6-D90A219F4C85}.Release|x64.ActiveCfg = Release|x64
     39    {07C05C8F-0769-4607-96C6-D90A219F4C85}.Release|x64.Build.0 = Release|x64
     40    {07C05C8F-0769-4607-96C6-D90A219F4C85}.Release|x86.ActiveCfg = Release|x86
     41    {07C05C8F-0769-4607-96C6-D90A219F4C85}.Release|x86.Build.0 = Release|x86
    4042  EndGlobalSection
    4143  GlobalSection(SolutionProperties) = preSolution
  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Matching/SymbolicExpressionTreeNodeComparer.cs

    r11486 r11894  
    2121
    2222using System;
     23using System.Collections.Generic;
    2324using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    2425
     
    2930  // - used for bringing subtrees to a "canonical" form when the operation allows reordering of arguments
    3031  public class SymbolicExpressionTreeNodeComparer : ISymbolicExpressionTreeNodeComparer {
    31     public int Compare(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
     32    public static int Compare(ISymbolicExpressionTreeNode a, ISymbolicExpressionTreeNode b) {
    3233      var ta = a as SymbolicExpressionTreeTerminalNode;
    3334      var tb = b as SymbolicExpressionTreeTerminalNode;
     
    6465      return result == 0 ? a.Weight.CompareTo(b.Weight) : result;
    6566    }
     67
     68    int IComparer<ISymbolicExpressionTreeNode>.Compare(ISymbolicExpressionTreeNode x, ISymbolicExpressionTreeNode y) {
     69      return Compare(x, y);
     70    }
    6671  }
    6772
  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/SimilarityCalculators/BottomUpSimilarityCalculator.cs

    r11889 r11894  
    8383      var nodes1 = n1.IterateNodesPrefix().ToList();
    8484      var nodes2 = n2.IterateNodesPrefix().ToList();
    85       foreach (var v in nodes1) {
     85      for (int i = 0; i < nodes1.Count; ++i) {
     86        var v = nodes1[i];
    8687        if (forwardMap.ContainsKey(v))
    8788          continue;
    8889        var kv = compactedGraph[v];
    8990        ISymbolicExpressionTreeNode w = null;
    90         foreach (var t in nodes2) {
     91        for (int j = 0; j < nodes2.Count; ++j) {
     92          var t = nodes2[j];
    9193          if (reverseMap.ContainsKey(t) || compactedGraph[t] != kv)
    9294            continue;
     
    98100        // 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)
    99101        // 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
    100         var eV = IterateBreadthOrdered(v, comparer).GetEnumerator();
    101         var eW = IterateBreadthOrdered(w, comparer).GetEnumerator();
    102 
    103         while (eV.MoveNext() && eW.MoveNext()) {
    104           var s = eV.Current;
    105           var t = eW.Current;
    106 
     102        var vv = IterateBreadthOrdered(v, comparer).ToList();
     103        var ww = IterateBreadthOrdered(w, comparer).ToList();
     104        int len = Math.Min(vv.Count, ww.Count);
     105        for (int j = 0; j < len; ++j) {
     106          var s = vv[j];
     107          var t = ww[j];
    107108          Debug.Assert(!reverseMap.ContainsKey(t));
    108109
     
    136137            var z = new GraphNode { SymbolicExpressionTreeNode = n, Label = label };
    137138            labelMap[z.Label] = z;
    138             list.Add(z);
    139139          }
    140140          nodeMap[n] = labelMap[label];
     
    146146      while (queue.Any()) {
    147147        var n = queue.Dequeue();
    148 
    149148        if (n.SubtreeCount > 0) {
     149          bool found = false;
    150150          var label = n.Symbol.Name;
    151           bool found = false;
    152151          var depth = n.GetDepth();
    153152
    154           bool sort = commutativeSymbols.Contains(label);
    155           var nNodes = n.Subtrees.Select(x => nodeMap[x]).ToList();
    156           if (sort) nNodes.Sort((a, b) => string.CompareOrdinal(a.Label, b.Label));
     153          bool sort = n.SubtreeCount > 1 && commutativeSymbols.Contains(label);
     154          var nSubtrees = n.Subtrees.Select(x => nodeMap[x]).ToList();
     155          if (sort) nSubtrees.Sort((a, b) => string.CompareOrdinal(a.Label, b.Label));
    157156
    158157          for (int i = list.Count - 1; i >= 0; --i) {
    159158            var w = list[i];
    160 
    161             if (!(n.SubtreeCount == w.ChildrenCount && label == w.Label && depth == w.Depth))
     159            if (!(n.SubtreeCount == w.SubtreeCount && label == w.Label && depth == w.Depth))
    162160              continue;
    163161
    164162            // sort V and W when the symbol is commutative because we are dealing with unordered trees
    165163            var m = w.SymbolicExpressionTreeNode;
    166             var mNodes = m.Subtrees.Select(x => nodeMap[x]).ToList();
    167             if (sort) mNodes.Sort((a, b) => string.CompareOrdinal(a.Label, b.Label));
    168 
    169             if (nNodes.SequenceEqual(mNodes)) {
     164            var mSubtrees = m.Subtrees.Select(x => nodeMap[x]).ToList();
     165            if (sort) mSubtrees.Sort((a, b) => string.CompareOrdinal(a.Label, b.Label));
     166
     167            found = nSubtrees.SequenceEqual(mSubtrees);
     168            if (found) {
    170169              nodeMap[n] = w;
    171               found = true;
    172170              break;
    173171            }
     
    230228      public string Label;
    231229      public int Depth;
    232       public int ChildrenCount { get { return SymbolicExpressionTreeNode.SubtreeCount; } }
     230      public int SubtreeCount { get { return SymbolicExpressionTreeNode.SubtreeCount; } }
    233231    }
    234232  }
  • branches/HeuristicLab.BottomUpTreeDistance/HeuristicLab.Tests/BottomUpTreeSimilarityCalculatorTest.cs

    r11486 r11894  
    1717    private readonly SymbolicExpressionImporter importer;
    1818
    19     private const int N = 100;
     19    private const int N = 150;
    2020    private const int Rows = 1;
    2121    private const int Columns = 10;
Note: See TracChangeset for help on using the changeset viewer.