TreeSimplifier performance gets worse the deeper a tree is nested

[mkommend]

Currently the tree simplifier cannot simplify a tree with a tree depth above 40. At least not the tree I encountered (see attached sample file), because it was calculating more than 12 hours.

[mkommend]

File containing a tree that cannot be simplified

[mkommend]

r12227: Improved performance of symbolic expression tree simplifier.

The attached sample tree is now simplified in under a second. r12227 introduces ToArray calls in the linq queries (simplification of +, -, *, /), but I am still unsure why the laziness of the linq queries caused the slow performance.

[gkronber]

r12262: implemented a fix for the performance problem without a call to .ToArray() (overwrites changes of r12227)

[gkronber]

The reason for the performance problem is that we evaluate GetSimplifiedTree twice for the first element for the simplification of subtraction and division because of the call to .First() and .Skip(1). Additionally, this is only a problem if we have trees that are deeply nested to the left.

using System;
using System.Linq;
using System.Collections.Generic;

using HeuristicLab.Core;
using HeuristicLab.Common;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
using HeuristicLab.Problems.DataAnalysis.Symbolic;

public class MyScript : HeuristicLab.Scripting.CSharpScriptBase {
  public override void Main() {
    // type your code here
    var varNode = (VariableTreeNode)new HeuristicLab.Problems.DataAnalysis.Symbolic.Variable("a", "a").CreateTreeNode();
    varNode.VariableName = "a";
    varNode.Weight = 1.0;
    var treeNode = (ISymbolicExpressionTreeNode)varNode;
    for(int i = 0; i< 40; i++) {
      treeNode = MakeSum(2.0, treeNode);
    }
    
    var start = new StartSymbol().CreateTreeNode();
    var root = new ProgramRootSymbol().CreateTreeNode();
    root.AddSubtree(start);
    start.AddSubtree(treeNode);
    treeNode = root;
    
    SymbolicDataAnalysisExpressionTreeSimplifier simpl = new SymbolicDataAnalysisExpressionTreeSimplifier();
    var simplified = simpl.GetSimplifiedTree(treeNode);
    
    var simpleTree = new SymbolicExpressionTree(simplified);
    var tree = new SymbolicExpressionTree(treeNode);    
    vars["simpleTree"] = simpleTree;
    vars["tree"] = tree;
  }

  public ISymbolicExpressionTreeNode MakeSum(double x, ISymbolicExpressionTreeNode  tree) {
    var c = (ConstantTreeNode)(new HeuristicLab.Problems.DataAnalysis.Symbolic.Constant().CreateTreeNode());
    c.Value = x;
    var p = new Subtraction().CreateTreeNode();         // subtraction uses a skip(1)
    // this variant works 
    // p.AddSubtree(c);
    // p.AddSubtree(tree);

    // this variant is slow 
    p.AddSubtree(tree);
    p.AddSubtree(c);

    return p;
  }
}

[gkronber]

r12264: fixed a bug in the simplifier introduced with r12262 (an a few minor code improvments)

[mkommend]

Reviewed r12262 & r12264.

[mkommend]

r12277: Merged r12227, r12262 and r12264 into stable.