Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
02/02/15 13:17:23 (10 years ago)
Author:
bburlacu
Message:

#1772: Improved TraceCalculator performance by caching node lists (2.5-3x speed increase). Removed old tracing code. Insignificant change to the SymbolicDataAnalysisExpressionBeforeManipulatorOperator (rephrased a comment).

Location:
branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking
Files:
1 deleted
2 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/SymbolicDataAnalysisExpressionBeforeManipulatorOperator.cs

    r11694 r11855  
    4747      //    the cloning will also clone the vertex data object, therefore reference comparison of node lists will not work
    4848      // 2) replaces the parent of the current individual with the clone, and alters graph connections accordingly
    49       //    therefore, vChild will be the vertex of the child, and vClone the vertex of the cloned parent
     49      //    so that vChild vertex will represent the child, and vClone will represent the cloned parent
    5050      var result = base.Apply();
    5151      var vChild = GenealogyGraph.GetByContent(ChildParameter.ActualValue);
  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/TraceCalculator.cs

    r11852 r11855  
    3636    private IGenealogyGraph<ISymbolicExpressionTree> traceGraph;
    3737    private Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, Tuple<int, int>> traceMap;
     38    private Dictionary<ISymbolicExpressionTree, List<ISymbolicExpressionTreeNode>> nodeListCache;
    3839
    3940    public IGenealogyGraph<ISymbolicExpressionTree> TraceGraph { get { return traceGraph; } }
     
    4243      traceGraph = new GenealogyGraph<ISymbolicExpressionTree>();
    4344      traceMap = new Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, Tuple<int, int>>();
     45      nodeListCache = new Dictionary<ISymbolicExpressionTree, List<ISymbolicExpressionTreeNode>>();
    4446    }
    4547
     
    6870      traceGraph = new GenealogyGraph<ISymbolicExpressionTree>();
    6971      traceMap = new Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, Tuple<int, int>>();
     72      nodeListCache = new Dictionary<ISymbolicExpressionTree, List<ISymbolicExpressionTreeNode>>();
    7073      TraceRecursive(node, subtreeIndex);
    7174      return traceGraph;
     
    100103        var fragment = (IFragment<ISymbolicExpressionTreeNode>)g.InArcs.Last().Data;
    101104        if (fragment == null) {
    102           //          if (parents.Count == 2)
    103           //            throw new Exception("There should always be a crossover fragment.");
     105          // TODO: think about what the correct behavior should be here (seems good so far)
    104106          // the node is either an elite node or (in rare cases) no fragment was transferred
    105107          g = parents[0];
     
    109111        int fi = fragment.Index1;               // fragment index
    110112        int fl = fragment.Root.GetLength();     // fragment length
    111         int sl = g.Data.NodeAt(si).GetLength(); // subtree length
     113        int sl = NodeAt(g.Data, si).GetLength(); // subtree length
    112114
    113115        #region trace crossover
     
    126128              // fragment distinct from subtree
    127129              g = parents[0];
    128               si += g.Data.NodeAt(fi).GetLength() - fl;
     130              si += NodeAt(g.Data, fi).GetLength() - fl;
    129131            }
    130132            continue;
     
    160162            g = parents[0];
    161163            if (fi < si)
    162               si += g.Data.NodeAt(fi).GetLength() - fl;
     164              si += NodeAt(g.Data, fi).GetLength() - fl;
    163165            continue;
    164166          }
     
    188190      }
    189191      return n;
     192    }
     193
     194    // caching node lists brings ~2.5-2.7x speed improvement (since graph nodes are visited multiple times)
     195    // this caching will be even more effective with larger tree sizes
     196    private ISymbolicExpressionTreeNode NodeAt(ISymbolicExpressionTree tree, int index) {
     197      List<ISymbolicExpressionTreeNode> list;
     198      nodeListCache.TryGetValue(tree, out list);
     199      if (list == null) {
     200        list = tree.IterateNodesPrefix().ToList();
     201        nodeListCache[tree] = list;
     202      }
     203      return list[index];
    190204    }
    191205
     
    221235      return new GenealogyGraphNode<ISymbolicExpressionTree>(node.Data) { Rank = node.Rank, Quality = node.Quality };
    222236    }
    223     public static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTree tree, int index) {
    224       return NodeAt(tree.Root, index);
    225     }
    226     public static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTreeNode root, int index) {
    227       return root.IterateNodesPrefix().ElementAt(index);
    228     }
    229237    #endregion
    230238  }
Note: See TracChangeset for help on using the changeset viewer.