Changeset 11855

Timestamp:

02/02/15 13:17:23 (9 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:

• SymbolicDataAnalysisExpressionBeforeManipulatorOperator.cs (modified) (1 diff)
• SymbolicDataAnalysisExpressionTracing.cs (deleted)
• TraceCalculator.cs (modified) (9 diffs)

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

@@ -47 +47 @@
       //    the cloning will also clone the vertex data object, therefore reference comparison of node lists will not work
       // 2) replaces the parent of the current individual with the clone, and alters graph connections accordingly
-      //    therefore, vChild will be the vertex of the child, and vClone the vertex of the cloned parent
+      //    so that vChild vertex will represent the child, and vClone will represent the cloned parent
       var result = base.Apply();
       var vChild = GenealogyGraph.GetByContent(ChildParameter.ActualValue);

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

@@ -36 +36 @@
     private IGenealogyGraph<ISymbolicExpressionTree> traceGraph;
     private Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, Tuple<int, int>> traceMap;
+    private Dictionary<ISymbolicExpressionTree, List<ISymbolicExpressionTreeNode>> nodeListCache;
 
     public IGenealogyGraph<ISymbolicExpressionTree> TraceGraph { get { return traceGraph; } }
@@ -42 +43 @@
       traceGraph = new GenealogyGraph<ISymbolicExpressionTree>();
       traceMap = new Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, Tuple<int, int>>();
+      nodeListCache = new Dictionary<ISymbolicExpressionTree, List<ISymbolicExpressionTreeNode>>();
     }
 
@@ -68 +70 @@
       traceGraph = new GenealogyGraph<ISymbolicExpressionTree>();
       traceMap = new Dictionary<IGenealogyGraphNode<ISymbolicExpressionTree>, Tuple<int, int>>();
+      nodeListCache = new Dictionary<ISymbolicExpressionTree, List<ISymbolicExpressionTreeNode>>();
       TraceRecursive(node, subtreeIndex);
       return traceGraph;
@@ -100 +103 @@
         var fragment = (IFragment<ISymbolicExpressionTreeNode>)g.InArcs.Last().Data;
         if (fragment == null) {
-          //          if (parents.Count == 2)
-          //            throw new Exception("There should always be a crossover fragment.");
+          // TODO: think about what the correct behavior should be here (seems good so far)
           // the node is either an elite node or (in rare cases) no fragment was transferred
           g = parents[0];
@@ -109 +111 @@
         int fi = fragment.Index1;               // fragment index
         int fl = fragment.Root.GetLength();     // fragment length
-        int sl = g.Data.NodeAt(si).GetLength(); // subtree length
+        int sl = NodeAt(g.Data, si).GetLength(); // subtree length
 
         #region trace crossover
@@ -126 +128 @@
               // fragment distinct from subtree
               g = parents[0];
-              si += g.Data.NodeAt(fi).GetLength() - fl;
+              si += NodeAt(g.Data, fi).GetLength() - fl;
             }
             continue;
@@ -160 +162 @@
             g = parents[0];
             if (fi < si)
-              si += g.Data.NodeAt(fi).GetLength() - fl;
+              si += NodeAt(g.Data, fi).GetLength() - fl;
             continue;
           }
@@ -188 +190 @@
       }
       return n;
+    }
+
+    // caching node lists brings ~2.5-2.7x speed improvement (since graph nodes are visited multiple times)
+    // this caching will be even more effective with larger tree sizes
+    private ISymbolicExpressionTreeNode NodeAt(ISymbolicExpressionTree tree, int index) {
+      List<ISymbolicExpressionTreeNode> list;
+      nodeListCache.TryGetValue(tree, out list);
+      if (list == null) {
+        list = tree.IterateNodesPrefix().ToList();
+        nodeListCache[tree] = list;
+      }
+      return list[index];
     }
 
@@ -221 +235 @@
       return new GenealogyGraphNode<ISymbolicExpressionTree>(node.Data) { Rank = node.Rank, Quality = node.Quality };
     }
-    public static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTree tree, int index) {
-      return NodeAt(tree.Root, index);
-    }
-    public static ISymbolicExpressionTreeNode NodeAt(this ISymbolicExpressionTreeNode root, int index) {
-      return root.IterateNodesPrefix().ElementAt(index);
-    }
     #endregion
   }