Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
02/11/15 12:39:20 (10 years ago)
Author:
bburlacu
Message:

#1772: Improve performance of the TraceCalculator by marking visited trace nodes to avoid duplicate effort.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/TraceCalculator.cs

    r11968 r11979  
    3434  [StorableClass]
    3535  public class TraceCalculator : Item {
    36     private IGenealogyGraph<ISymbolicExpressionTree> traceGraph;
    3736    private Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, TraceData> traceMap;
    3837    private Dictionary<ISymbolicExpressionTree, List<ISymbolicExpressionTreeNode>> nodeListCache;
    39 
    40     public IGenealogyGraph<ISymbolicExpressionTree> TraceGraph { get { return traceGraph; } }
     38    private HashSet<Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>> traceCache;
     39    public IGenealogyGraph<ISymbolicExpressionTree> TraceGraph { get; private set; }
    4140
    4241    public TraceCalculator() {
    43       traceGraph = new GenealogyGraph<ISymbolicExpressionTree>();
     42      TraceGraph = new GenealogyGraph<ISymbolicExpressionTree>();
    4443      traceMap = new Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, TraceData>();
    4544      nodeListCache = new Dictionary<ISymbolicExpressionTree, List<ISymbolicExpressionTreeNode>>();
     45      traceCache = new HashSet<Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>>();
    4646    }
    4747
    … …  
    5454    }
    5555
    56     public static IGenealogyGraph<ISymbolicExpressionTree> TraceSubtree(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex) {
     56    public static IGenealogyGraph<ISymbolicExpressionTree> TraceSubtree(
     57      IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex) {
    5758      var tc = new TraceCalculator();
    5859      tc.Trace(node, subtreeIndex);
    … …  
    6162
    6263    public IGenealogyGraph<ISymbolicExpressionTree> Trace(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex) {
    63       traceGraph = new GenealogyGraph<ISymbolicExpressionTree>();
     64      TraceGraph = new GenealogyGraph<ISymbolicExpressionTree>();
    6465      traceMap = new Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, TraceData>();
    6566      nodeListCache = new Dictionary<ISymbolicExpressionTree, List<ISymbolicExpressionTreeNode>>();
     67      traceCache = new HashSet<Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>>();
    6668      TraceRecursive(node, subtreeIndex);
    67       return traceGraph;
     69      return TraceGraph;
    6870    }
    6971
    … …  
    8890    /// <param name="subtreeIndex">The index of the traced subtree</param>
    8991    /// <param name="last">The last added node in the trace graph</param>
    90     private void TraceRecursive(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex, IGenealogyGraphNode<ISymbolicExpressionTree> last = null) {
     92    private void TraceRecursive(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex,
     93      IGenealogyGraphNode<ISymbolicExpressionTree> last = null) {
    9194      var g = node;
    9295      int si = subtreeIndex; // subtree index
    … …  
    104107        }
    105108
    106         fi = fragment.Index1;               // fragment index
    107         int fl = fragment.Root.GetLength();     // fragment length
     109        fi = fragment.Index1; // fragment index
     110        int fl = fragment.Root.GetLength(); // fragment length
    108111        int sl = NodeAt(g.Data, si).GetLength(); // subtree length
    109112
    110113        #region trace crossover
     114
    111115        if (inArcs.Count == 2) {
    112116          var parent0 = (IGenealogyGraphNode<ISymbolicExpressionTree>)inArcs[0].Source;
    … …  
    133137              // subtree contains fragment => branching point in the fragment graph
    134138              var n = AddTraceNode(g, si, fi); // current node becomes "last" as we restart tracing from the parent
    135               TraceRecursive(parent0, si, n);
    136               TraceRecursive(parent1, fragment.Index2, n);
     139              var t0 = new Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>(parent0, n, si);
     140              if (!traceCache.Contains(t0)) {
     141                TraceRecursive(parent0, si, n);
     142                traceCache.Add(t0);
     143              } else {
     144                n.Weight++;
     145              }
     146              var t1 = new Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>(parent1, n, fragment.Index2);
     147              if (!traceCache.Contains(t1)) {
     148                TraceRecursive(parent1, fragment.Index2, n);
     149                traceCache.Add(t1);
     150              } else {
     151                n.Weight++;
     152              }
    137153              break;
    138154            } else {
    … …  
    154170            var n = AddTraceNode(g, si, fi); // current node becomes "last" as we restart tracing from the parent
    155171            int i = si < fi ? si : fi;
    156             TraceRecursive(parent0, i, n);
     172            var t = new Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>(parent0, n, i);
     173            if (!traceCache.Contains(t)) {
     174              TraceRecursive(parent0, i, n);
     175              traceCache.Add(t);
     176            } else {
     177              n.Weight++;
     178            }
    157179            break;
    158180          } else {
    … …  
    182204    /// <param name="fi">The fragment index</param>
    183205    /// <returns></returns>
    184     private IGenealogyGraphNode<ISymbolicExpressionTree> AddTraceNode(IGenealogyGraphNode<ISymbolicExpressionTree> g, int si, int fi) {
    185       var n = traceGraph.GetByContent(g.Data);
     206    private IGenealogyGraphNode<ISymbolicExpressionTree> AddTraceNode(IGenealogyGraphNode<ISymbolicExpressionTree> g,
     207      int si, int fi) {
     208      var n = TraceGraph.GetByContent(g.Data);
    186209      if (n == null) {
    187210        n = g.Copy();
    188         traceGraph.AddVertex(n);
     211        TraceGraph.AddVertex(n);
    189212        Debug.Assert(!traceMap.ContainsKey(n));
    190213        traceMap[n] = new TraceData(si, fi, -1, -1); // only the first two fields are needed
    … …  
    213236    /// <param name="si">The index of the traced subtree</param>
    214237    /// <param name="fi">The index of the fragment</param>
    215     private void ConnectLast(IGenealogyGraphNode<ISymbolicExpressionTree> current, IGenealogyGraphNode<ISymbolicExpressionTree> last, int si, int fi) {
     238    private void ConnectLast(IGenealogyGraphNode<ISymbolicExpressionTree> current,
     239      IGenealogyGraphNode<ISymbolicExpressionTree> last, int si, int fi) {
    216240      var lastTraceData = traceMap[last];
    217       int lastSi = lastTraceData.SubtreeIndex; // last subtree index (index of the traced subtree in the previous trace node)
    218       int lastFi = lastTraceData.FragmentIndex; // last fragment index (index of the fragment in the previous trace node)
     241      int lastSi = lastTraceData.SubtreeIndex;
     242      // last subtree index (index of the traced subtree in the previous trace node)
     243      int lastFi = lastTraceData.FragmentIndex;
     244      // last fragment index (index of the fragment in the previous trace node)
    219245      var td = new TraceData(si, fi, lastSi, lastFi); // trace data
    220       //var arc = current.OutArcs.SingleOrDefault(a => a.Target == last && a.Data.Equals(td));
    221       var outArcs = (List<IArc>)((IVertex)current).OutArcs;
    222       var arc = outArcs.FirstOrDefault(a => a.Target == last && ((IArc<IDeepCloneable>)a).Data.Equals(td));
     246      // using the inArcs seems to be slightly more efficient than using the outArcs
     247      // TODO: more testing
     248      var inArcs = (List<IArc>)((IVertex)last).InArcs;
     249      var arc = inArcs.FirstOrDefault(a => a.Source == current && ((IArc<IDeepCloneable>)a).Data.Equals(td));
    223250      if (arc == null) {
    224251        arc = new GenealogyGraphArc(current, last) { Data = td };
    225         traceGraph.AddArc(arc);
     252        TraceGraph.AddArc(arc);
    226253      }
    227254    }
    228255  }
    229   // this class is here to help clarify the semantics
     256
    230257  public class TraceData : Tuple<int, int, int, int>, IDeepCloneable {
    231258    public TraceData(int currentSubtreeIndex, int currentFragmentIndex, int lastSubtreeIndex, int lastFragmentIndex)
Note: See TracChangeset for help on using the changeset viewer.