Changeset 14745 for branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Expressions/PushProgram.cs

Timestamp:

03/11/17 12:42:31 (7 years ago)

Author:

pkimmesw

Message:

#2665 Merged ExecExpandExpression and PushProgram due to performance reasons, Tested managed object pooling

File:

• branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Expressions/PushProgram.cs (modified) (14 diffs)

branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Expressions/PushProgram.cs

@@ -1 @@
-using System.Collections.Generic;
+using System;
+using System.Collections.Generic;
+using System.Linq;
 
 namespace HeuristicLab.Problems.ProgramSynthesis.Push.Expressions {
   using System.Diagnostics;
-  using System.Linq;
-
-  public class PushProgram {
+
+  using Interpreter;
+
+  public class PushProgram : StatefulExpression<Expression[]> {
+    public static readonly PushProgram Empty = new PushProgram();
 
     private const string Prefix = "(";
@@ -13 +17 @@
     private const string Delimiter = " ";
 
-    public static readonly PushProgram Empty = new PushProgram(new Expression[0]);
-
-    public readonly IReadOnlyList<Expression> Expressions;
-    public bool IsEmpty { get; private set; }
-
-    public PushProgram(Expression[] expressions) {
-      this.Expressions = expressions;
-      this.IsEmpty = expressions.Length == 0;
+    public readonly bool IsEmpty;
+
+    public PushProgram(params Expression[] state) : base(state) {
+      IsEmpty = state.Length == 0;
+    }
+
+    public PushProgram(IEnumerable<Expression> state) : this(state.ToArray()) {
+      // TODO: lazy evaluation of ToArray()
     }
 
     private string stringRepresentation;
-    private string StringRepresentation
+    public override string StringRepresentation
     {
       get
@@ -35 +39 @@
 
     private int depth = -1;
-    private int Depth
+    public int Depth
     {
       get
@@ -44 +48 @@
     }
 
-    private int[] treeIndex = null;
-    public int[] TreeIndex
-    {
-      get
-      {
-        return this.treeIndex ?? (this.treeIndex = this.BuildTreeIndex());
+    private int[] treeIndex;
+    private int[] TreeIndex
+    {
+      get
+      {
+        return treeIndex ?? (treeIndex = BuildTreeIndex());
       }
     }
@@ -61 +65 @@
         return hashCode;
       }
+    }
+
+    //public PushProgram Copy() {
+    //  // as the empty list is a static stateless expression, no copy required
+    //  return ReferenceEquals(this, Empty) || this.State.IsEmpty
+    //    ? Empty
+    //    : new PushProgram(this.State.Copy());
+    //}
+
+    public override bool Eval(IPushInterpreter interpreter) {
+      interpreter.ExecStack.Push(this.State);
+      return true;
     }
 
@@ -87 +103 @@
 
     public IEnumerable<Expression> DepthFirst() {
-      foreach (var expr in this.Expressions) {
+      foreach (var expr in this.State) {
         if (expr.CanExpand) {
-          var expandExpr = (ExecExpandExpression)expr;
-
-          foreach (var sub in expandExpr.State.DepthFirst())
+          var expandExpr = (PushProgram)expr;
+
+          foreach (var sub in expandExpr.DepthFirst())
             yield return sub;
         } else yield return expr;
@@ -98 +114 @@
 
     public PushProgram Copy() {
-      return IsEmpty ? this : new PushProgram((Expression[])Expressions) {
+      return IsEmpty ? this : new PushProgram(State) {
         stringRepresentation = this.stringRepresentation,
         hashCode = this.hashCode,
@@ -106 +122 @@
     }
 
-    public Expression[] CopyExpressions() {
-      var copy = new Expression[this.Expressions.Count];
-      ((Expression[])this.Expressions).CopyTo(copy, Expressions.Count);
+    public Expression[] CopyExpressions()
+    {
+      if (IsEmpty) return Empty.State;
+
+      var copy = new Expression[State.Length];
+      State.CopyTo(copy, 0);
 
       return copy;
@@ -114 +133 @@
 
     private int CalcDepth() {
-      //var subExpressions = Expressions.Where(e => e.CanExpand);
-      //var depth = subExpressions.Any()
-      //    ? subExpressions.Select(e => e as ExecExpandExpression).Max(e => e.State.Depth) + 1
-      //    : 1;
-
-      ////return depth;
-
       var maxDepth = 1;
-      for (var i = 0; i < Expressions.Count; i++) {
-        var expression = Expressions[i];
+      for (var i = 0; i < State.Length; i++) {
+        var expression = State[i];
         if (!expression.CanExpand) continue;
-        var expandExpression = (ExecExpandExpression)expression;
-
-        if (expandExpression.State.Depth > maxDepth)
-          maxDepth = expandExpression.State.Depth;
+        var expandExpression = (PushProgram)expression;
+
+        if (expandExpression.Depth > maxDepth)
+          maxDepth = expandExpression.Depth;
       }
 
@@ -137 +149 @@
       // prevent too big string
       return this.TotalCount > 50
-        ? PrefixReduced + this.Expressions.Count + PostfixReduced
-        : Prefix + string.Join(Delimiter, this.Expressions.Where(e => !string.IsNullOrWhiteSpace(e.StringRepresentation))) + Postfix;
+        ? PrefixReduced + this.State.Length + PostfixReduced
+        : Prefix + string.Join(Delimiter, this.State.Where(e => !string.IsNullOrWhiteSpace(e.StringRepresentation))) + Postfix;
     }
 
     private int[] BuildTreeIndex() {
-      var local_treeIndex = new int[this.Expressions.Count];
+      var local_treeIndex = new int[State.Length];
 
       var next = 1;
 
-      for (var i = this.Expressions.Count - 1; i >= 0; i--) {
-        var subExpression = this.Expressions[i];
+      for (var i = State.Length - 1; i >= 0; i--) {
+        var subExpression = State[i];
 
         local_treeIndex[i] = next;
 
         if (subExpression.CanExpand) {
-          next += ((ExecExpandExpression)subExpression).State.TotalCount;
+          next += ((PushProgram)subExpression).TotalCount;
         } else {
           next++;
@@ -164 +176 @@
       var hash = 19 * 31 + this.GetType().FullName.GetHashCode();
 
-      for (var i = 0; i < this.Expressions.Count; i++) {
-        hash = hash * 31 + this.Expressions[i].GetHashCode();
+      for (var i = 0; i < State.Length; i++) {
+        hash = hash * 31 + State[i].GetHashCode();
       }
 
@@ -171 +183 @@
     }
 
-    private static void CheckIfNested(int level, ExecExpandExpression target, ExecExpandExpression current,
-        IList<ExecExpandExpression> visited) {
+    private static void CheckIfNested(int level, PushProgram target, PushProgram current,
+        IList<PushProgram> visited) {
       if (visited.Any(x => ReferenceEquals(x, current)))
         Debugger.Break();
@@ -183 +195 @@
       }
 
-      for (var i = 0; i < current.State.Expressions.Count; i++) {
-        if (current.State.Expressions[i].CanExpand)
+      for (var i = 0; i < current.State.Length; i++) {
+        if (current.State[i].CanExpand)
           continue;
 
-        var subExpression = current.State.Expressions[i] as ExecExpandExpression;
+        var subExpression = current.State[i] as PushProgram;
 
         if (ReferenceEquals(target, subExpression)) {
@@ -199 +211 @@
       visited.RemoveAt(visited.Count - 1);
     }
+
+    /// <summary>
+    ///     Returns the element with the given index whereby the tree is indexed in depth first manner
+    /// </summary>
+    /// <param name="index">The index of the required element</param>
+    /// <returns>The required element</returns>
+    public Expression GetFromTree(int index) {
+      return GetFromTree(index, (root, parent, child, childIndex, parentIndex) => child);
+    }
+
+    /// <returns>The required element</returns>
+    public T GetFromTree<T>(int index,
+        Func<PushProgram, PushProgram, Expression, int, int, T> resolver) {
+      return GetFromTree(index, 0, null, resolver);
+    }
+
+    private T GetFromTree<T>(int index, int parentIndex, PushProgram parent,
+        Func<PushProgram, PushProgram, Expression, int, int, T> resolver) {
+      if (index == 0) return resolver(parent, parent, this, 0, parentIndex);
+
+      var min = State.Length - 1;
+      var max = 0;
+      var mid = (min + max) / 2;
+
+      while ((max <= min) && (TreeIndex[mid] != index)) {
+        if (TreeIndex[mid] > index) max = mid + 1;
+        else min = mid - 1;
+
+        mid = (min + max) / 2;
+      }
+
+      return TreeIndex[mid] == index
+          ? resolver(parent, this, State[mid], mid, parentIndex)
+          : (State[mid + 1] as PushProgram).GetFromTree(index - TreeIndex[mid + 1], mid + 1,
+              this, resolver);
+    }
   }
 }