Changeset 11979

Timestamp:

02/11/15 12:39:20 (9 years ago)

Author:

bburlacu

Message:

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

File:

• branches/HeuristicLab.EvolutionTracking/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Tracking/TraceCalculator.cs (modified) (9 diffs)

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

@@ -34 +34 @@
   [StorableClass]
   public class TraceCalculator : Item {
-    private IGenealogyGraph<ISymbolicExpressionTree> traceGraph;
     private Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, TraceData> traceMap;
     private Dictionary<ISymbolicExpressionTree, List<ISymbolicExpressionTreeNode>> nodeListCache;
-
-    public IGenealogyGraph<ISymbolicExpressionTree> TraceGraph { get { return traceGraph; } }
+    private HashSet<Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>> traceCache;
+    public IGenealogyGraph<ISymbolicExpressionTree> TraceGraph { get; private set; }
 
     public TraceCalculator() {
-      traceGraph = new GenealogyGraph<ISymbolicExpressionTree>();
+      TraceGraph = new GenealogyGraph<ISymbolicExpressionTree>();
       traceMap = new Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, TraceData>();
       nodeListCache = new Dictionary<ISymbolicExpressionTree, List<ISymbolicExpressionTreeNode>>();
+      traceCache = new HashSet<Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>>();
     }
 
@@ -54 +54 @@
     }
 
-    public static IGenealogyGraph<ISymbolicExpressionTree> TraceSubtree(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex) {
+    public static IGenealogyGraph<ISymbolicExpressionTree> TraceSubtree(
+      IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex) {
       var tc = new TraceCalculator();
       tc.Trace(node, subtreeIndex);
@@ -61 +62 @@
 
     public IGenealogyGraph<ISymbolicExpressionTree> Trace(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex) {
-      traceGraph = new GenealogyGraph<ISymbolicExpressionTree>();
+      TraceGraph = new GenealogyGraph<ISymbolicExpressionTree>();
       traceMap = new Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, TraceData>();
       nodeListCache = new Dictionary<ISymbolicExpressionTree, List<ISymbolicExpressionTreeNode>>();
+      traceCache = new HashSet<Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>>();
       TraceRecursive(node, subtreeIndex);
-      return traceGraph;
+      return TraceGraph;
     }
 
@@ -88 +90 @@
     /// <param name="subtreeIndex">The index of the traced subtree</param>
     /// <param name="last">The last added node in the trace graph</param>
-    private void TraceRecursive(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex, IGenealogyGraphNode<ISymbolicExpressionTree> last = null) {
+    private void TraceRecursive(IGenealogyGraphNode<ISymbolicExpressionTree> node, int subtreeIndex,
+      IGenealogyGraphNode<ISymbolicExpressionTree> last = null) {
       var g = node;
       int si = subtreeIndex; // subtree index
@@ -104 +107 @@
         }
 
-        fi = fragment.Index1;               // fragment index
-        int fl = fragment.Root.GetLength();     // fragment length
+        fi = fragment.Index1; // fragment index
+        int fl = fragment.Root.GetLength(); // fragment length
         int sl = NodeAt(g.Data, si).GetLength(); // subtree length
 
         #region trace crossover
+
         if (inArcs.Count == 2) {
           var parent0 = (IGenealogyGraphNode<ISymbolicExpressionTree>)inArcs[0].Source;
@@ -133 +137 @@
               // subtree contains fragment => branching point in the fragment graph
               var n = AddTraceNode(g, si, fi); // current node becomes "last" as we restart tracing from the parent
-              TraceRecursive(parent0, si, n);
-              TraceRecursive(parent1, fragment.Index2, n);
+              var t0 = new Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>(parent0, n, si);
+              if (!traceCache.Contains(t0)) {
+                TraceRecursive(parent0, si, n);
+                traceCache.Add(t0);
+              } else {
+                n.Weight++;
+              }
+              var t1 = new Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>(parent1, n, fragment.Index2);
+              if (!traceCache.Contains(t1)) {
+                TraceRecursive(parent1, fragment.Index2, n);
+                traceCache.Add(t1);
+              } else {
+                n.Weight++;
+              }
               break;
             } else {
@@ -154 +170 @@
             var n = AddTraceNode(g, si, fi); // current node becomes "last" as we restart tracing from the parent
             int i = si < fi ? si : fi;
-            TraceRecursive(parent0, i, n);
+            var t = new Tuple<IGenealogyGraphNode<ISymbolicExpressionTree>, IGenealogyGraphNode<ISymbolicExpressionTree>, int>(parent0, n, i);
+            if (!traceCache.Contains(t)) {
+              TraceRecursive(parent0, i, n);
+              traceCache.Add(t);
+            } else {
+              n.Weight++;
+            }
             break;
           } else {
@@ -182 +204 @@
     /// <param name="fi">The fragment index</param>
     /// <returns></returns>
-    private IGenealogyGraphNode<ISymbolicExpressionTree> AddTraceNode(IGenealogyGraphNode<ISymbolicExpressionTree> g, int si, int fi) {
-      var n = traceGraph.GetByContent(g.Data);
+    private IGenealogyGraphNode<ISymbolicExpressionTree> AddTraceNode(IGenealogyGraphNode<ISymbolicExpressionTree> g,
+      int si, int fi) {
+      var n = TraceGraph.GetByContent(g.Data);
       if (n == null) {
         n = g.Copy();
-        traceGraph.AddVertex(n);
+        TraceGraph.AddVertex(n);
         Debug.Assert(!traceMap.ContainsKey(n));
         traceMap[n] = new TraceData(si, fi, -1, -1); // only the first two fields are needed
@@ -213 +236 @@
     /// <param name="si">The index of the traced subtree</param>
     /// <param name="fi">The index of the fragment</param>
-    private void ConnectLast(IGenealogyGraphNode<ISymbolicExpressionTree> current, IGenealogyGraphNode<ISymbolicExpressionTree> last, int si, int fi) {
+    private void ConnectLast(IGenealogyGraphNode<ISymbolicExpressionTree> current,
+      IGenealogyGraphNode<ISymbolicExpressionTree> last, int si, int fi) {
       var lastTraceData = traceMap[last];
-      int lastSi = lastTraceData.SubtreeIndex; // last subtree index (index of the traced subtree in the previous trace node)
-      int lastFi = lastTraceData.FragmentIndex; // last fragment index (index of the fragment in the previous trace node)
+      int lastSi = lastTraceData.SubtreeIndex;
+      // last subtree index (index of the traced subtree in the previous trace node)
+      int lastFi = lastTraceData.FragmentIndex;
+      // last fragment index (index of the fragment in the previous trace node)
       var td = new TraceData(si, fi, lastSi, lastFi); // trace data
-      //var arc = current.OutArcs.SingleOrDefault(a => a.Target == last && a.Data.Equals(td));
-      var outArcs = (List<IArc>)((IVertex)current).OutArcs;
-      var arc = outArcs.FirstOrDefault(a => a.Target == last && ((IArc<IDeepCloneable>)a).Data.Equals(td));
+      // using the inArcs seems to be slightly more efficient than using the outArcs
+      // TODO: more testing
+      var inArcs = (List<IArc>)((IVertex)last).InArcs;
+      var arc = inArcs.FirstOrDefault(a => a.Source == current && ((IArc<IDeepCloneable>)a).Data.Equals(td));
       if (arc == null) {
         arc = new GenealogyGraphArc(current, last) { Data = td };
-        traceGraph.AddArc(arc);
+        TraceGraph.AddArc(arc);
       }
     }
   }
-  // this class is here to help clarify the semantics
+
   public class TraceData : Tuple<int, int, int, int>, IDeepCloneable {
     public TraceData(int currentSubtreeIndex, int currentFragmentIndex, int lastSubtreeIndex, int lastFragmentIndex)