Changeset 220 for branches/ExperimentalFunctionsBaking/BakedFunctionTree.cs

Timestamp:

05/07/08 00:02:43 (16 years ago)

Author:

gkronber

Message:

worked on #139:

• fixed display of trees in the gui
• split list representation of tree into two lists code and data
• implemented static evaluation for all predefined functions (except ProgrammableFunction)

File:

• branches/ExperimentalFunctionsBaking/BakedFunctionTree.cs (modified) (11 diffs)

branches/ExperimentalFunctionsBaking/BakedFunctionTree.cs

@@ -30 +30 @@
 namespace HeuristicLab.Functions {
   class BakedFunctionTree : ItemBase, IFunctionTree {
-    private List<double> code;
-    private static double nextFunctionSymbol = 10000;
-    private static Dictionary<double, IFunction> symbolTable = new Dictionary<double, IFunction>();
-    private static Dictionary<IFunction, double> reverseSymbolTable = new Dictionary<IFunction, double>();
-    private static double additionSymbol = -1;
-    private static double substractionSymbol = -1;
-    private static double multiplicationSymbol = -1;
-    private static double divisionSymbol = -1;
-    private static double variableSymbol = -1;
-    private static double constantSymbol = -1;
+    private List<int> code;
+    private List<double> data;
+    private const int ADDITION = 10010;
+    private const int AND = 10020;
+    private const int AVERAGE = 10030;
+    private const int CONSTANT = 10040;
+    private const int COSINUS = 10050;
+    private const int DIVISION = 10060;
+    private const int EQU = 10070;
+    private const int EXP = 10080;
+    private const int GT = 10090;
+    private const int IFTE = 10100;
+    private const int LT = 10110;
+    private const int LOG = 10120;
+    private const int MULTIPLICATION = 10130;
+    private const int NOT = 10140;
+    private const int OR = 10150;
+    private const int POWER = 10160;
+    private const int SIGNUM = 10170;
+    private const int SINUS = 10180;
+    private const int SQRT = 10190;
+    private const int SUBSTRACTION = 10200;
+    private const int TANGENS = 10210;
+    private const int VARIABLE = 10220;
+    private const int XOR = 10230;
+
+    private static int nextFunctionSymbol = 10240;
+    private static Dictionary<int, IFunction> symbolTable;
+    private static Dictionary<IFunction, int> reverseSymbolTable;
+    private static Dictionary<Type, int> staticTypes;
+
+    static BakedFunctionTree() {
+      symbolTable = new Dictionary<int, IFunction>();
+      reverseSymbolTable = new Dictionary<IFunction, int>();
+      staticTypes = new Dictionary<Type, int>();
+      staticTypes[typeof(Addition)] = ADDITION;
+      staticTypes[typeof(And)] = AND;
+      staticTypes[typeof(Average)] = AVERAGE;
+      staticTypes[typeof(Constant)] = CONSTANT;
+      staticTypes[typeof(Cosinus)] = COSINUS;
+      staticTypes[typeof(Division)] = DIVISION;
+      staticTypes[typeof(Equal)] = EQU;
+      staticTypes[typeof(Exponential)] = EXP;
+      staticTypes[typeof(GreaterThan)] = GT;
+      staticTypes[typeof(IfThenElse)] = IFTE;
+      staticTypes[typeof(LessThan)] = LT;
+      staticTypes[typeof(Logarithm)] = LOG;
+      staticTypes[typeof(Multiplication)] = MULTIPLICATION;
+      staticTypes[typeof(Not)] = NOT;
+      staticTypes[typeof(Or)] = OR;
+      staticTypes[typeof(Power)] = POWER;
+      staticTypes[typeof(Signum)] = SIGNUM;
+      staticTypes[typeof(Sinus)] = SINUS;
+      staticTypes[typeof(Sqrt)] = SQRT;
+      staticTypes[typeof(Substraction)] = SUBSTRACTION;
+      staticTypes[typeof(Tangens)] = TANGENS;
+      staticTypes[typeof(Variable)] = VARIABLE;
+      staticTypes[typeof(Xor)] = XOR;
+    }
 
     internal BakedFunctionTree() {
-      code = new List<double>();
+      code = new List<int>();
+      data = new List<double>();
     }
 
@@ -65 +115 @@
       code.Add(0);
       code.Add(MapFunction(tree.Function));
-      code.Add((byte)tree.LocalVariables.Count);
+      code.Add(tree.LocalVariables.Count);
       foreach(IVariable variable in tree.LocalVariables) {
         IItem value = variable.Value;
-        code.Add(GetDoubleValue(value));
+        data.Add(GetDoubleValue(value));
       }
       foreach(IFunctionTree subTree in tree.SubTrees) {
@@ -87 +137 @@
     }
 
-    private double MapFunction(IFunction function) {
+    private int MapFunction(IFunction function) {
       if(!reverseSymbolTable.ContainsKey(function)) {
-        reverseSymbolTable[function] = nextFunctionSymbol;
-        symbolTable[nextFunctionSymbol] = function;
-        if(function is Variable) {
-          variableSymbol = nextFunctionSymbol;
-        } else if(function is Constant) {
-          constantSymbol = nextFunctionSymbol;
-        } else if(function is Addition) {
-          additionSymbol = nextFunctionSymbol;
-        } else if(function is Substraction) {
-          substractionSymbol = nextFunctionSymbol;
-        } else if(function is Multiplication) {
-          multiplicationSymbol = nextFunctionSymbol;
-        } else if(function is Division) {
-          divisionSymbol = nextFunctionSymbol;
-        } else throw new NotSupportedException("Unsupported function " + function);
-
-        nextFunctionSymbol++;
+        int curFunctionSymbol;
+        if(staticTypes.ContainsKey(function.GetType())) curFunctionSymbol = staticTypes[function.GetType()];
+        else {
+          curFunctionSymbol = nextFunctionSymbol;
+          nextFunctionSymbol++;
+        }
+        reverseSymbolTable[function] = curFunctionSymbol;
+        symbolTable[curFunctionSymbol] = function;
       }
       return reverseSymbolTable[function];
     }
 
-    private int BranchLength(int branchRoot) {
-      double arity = code[branchRoot];
-      int nLocalVariables = (int)code[branchRoot + 2];
-      int len = 3 + nLocalVariables;
-      int subBranchStart = branchRoot + len;
+    private void BranchLength(int branchRoot, out int codeLength, out int dataLength) {
+      int arity = code[branchRoot];
+      int nLocalVariables = code[branchRoot + 2];
+      codeLength = 3;
+      dataLength = nLocalVariables;
+      int subBranchStart = branchRoot + codeLength;
       for(int i = 0; i < arity; i++) {
-        int branchLen = BranchLength(subBranchStart);
-        len += branchLen;
-        subBranchStart += branchLen;
-      }
-      return len;
+        int branchCodeLength;
+        int branchDataLength;
+        BranchLength(subBranchStart, out branchCodeLength, out branchDataLength);
+        subBranchStart += branchCodeLength;
+        codeLength += branchCodeLength;
+        dataLength += branchDataLength;
+      }
     }
 
@@ -130 +174 @@
           subTree.FlattenTrees();
           code.AddRange(subTree.code);
+          data.AddRange(subTree.data);
         }
         treesExpanded = false;
@@ -139 +184 @@
       if(variablesExpanded) {
         code[2] = variables.Count;
-        int localVariableIndex = 3;
         foreach(IVariable variable in variables) {
-          code.Insert(localVariableIndex, GetDoubleValue(variable.Value));
-          localVariableIndex++;
+          data.Add(GetDoubleValue(variable.Value));
         }
         variablesExpanded = false;
@@ -155 +198 @@
         if(!treesExpanded) {
           subTrees = new List<IFunctionTree>();
-          double arity = code[0];
-          int nLocalVariables = (int)code[2];
-          int branchIndex = 3 + nLocalVariables;
+          int arity = code[0];
+          int nLocalVariables = code[2];
+          int branchIndex = 3;
+          int dataIndex = nLocalVariables; // skip my local variables to reach the local variables of the first branch
           for(int i = 0; i < arity; i++) {
             BakedFunctionTree subTree = new BakedFunctionTree();
-            int branchLen = BranchLength(branchIndex);
-            subTree.code = code.GetRange(branchIndex, branchLen);
-            branchIndex += branchLen;
+            int codeLength;
+            int dataLength;
+            BranchLength(branchIndex, out codeLength, out dataLength);
+            subTree.code = code.GetRange(branchIndex, codeLength);
+            subTree.data = data.GetRange(dataIndex, dataLength);
+            branchIndex += codeLength;
+            dataIndex += dataLength;
             subTrees.Add(subTree);
           }
           treesExpanded = true;
-          code.RemoveRange(3 + nLocalVariables, code.Count - (3 + nLocalVariables));
+          code.RemoveRange(3, code.Count - 3);
           code[0] = 0;
+          data.RemoveRange(nLocalVariables, data.Count - nLocalVariables);
         }
         return subTrees;
@@ -180 +229 @@
           variables = new List<IVariable>();
           IFunction function = symbolTable[code[1]];
-          int localVariableIndex = 3;
+          int localVariableIndex = 0;
           foreach(IVariableInfo variableInfo in function.VariableInfos) {
             if(variableInfo.Local) {
@@ -186 +235 @@
               IItem value = clone.Value;
               if(value is ConstrainedDoubleData) {
-                ((ConstrainedDoubleData)value).Data = code[localVariableIndex];
+                ((ConstrainedDoubleData)value).Data = data[localVariableIndex];
               } else if(value is ConstrainedIntData) {
-                ((ConstrainedIntData)value).Data = (int)code[localVariableIndex];
+                ((ConstrainedIntData)value).Data = (int)data[localVariableIndex];
               } else if(value is DoubleData) {
-                ((DoubleData)value).Data = code[localVariableIndex];
+                ((DoubleData)value).Data = data[localVariableIndex];
               } else if(value is IntData) {
-                ((IntData)value).Data = (int)code[localVariableIndex];
+                ((IntData)value).Data = (int)data[localVariableIndex];
               } else throw new NotSupportedException("Invalid local variable type for GP.");
               variables.Add(clone);
@@ -200 +249 @@
           variablesExpanded = true;
           code[2] = 0;
-          code.RemoveRange(3, variables.Count);
+          data.RemoveRange(0, variables.Count);
         }
         return variables;
@@ -211 +260 @@
 
     public IVariable GetLocalVariable(string name) {
-      throw new NotImplementedException();
+      foreach(IVariable var in LocalVariables) {
+        if(var.Name == name) return var;
+      }
+      return null;
     }
 
     public void AddVariable(IVariable variable) {
-      throw new NotImplementedException();
+      throw new NotSupportedException();
     }
 
     public void RemoveVariable(string name) {
-      throw new NotImplementedException();
+      throw new NotSupportedException();
     }
 
     public void AddSubTree(IFunctionTree tree) {
-      if(treesExpanded) {
-        subTrees.Add(tree);
-      } else {
-        //code.AddRange(((BakedFunctionTree)tree).code);
-        //code[0] = code[0] + 1;
-        throw new NotImplementedException();
-      }
+      if(!treesExpanded) throw new InvalidOperationException();
+      subTrees.Add(tree);
     }
 
     public void InsertSubTree(int index, IFunctionTree tree) {
-      if(treesExpanded) {
-        subTrees.Insert(index, tree);
-      } else {
-        //byte nLocalVariables = code[2];
-        //// skip branches
-        //int currentBranchIndex = 3 + nLocalVariables;
-        //for(int i = 0; i < index; i++) {
-        //  int branchLength = BranchLength(currentBranchIndex);
-        //  currentBranchIndex += branchLength;
-        //}
-
-        //code.InsertRange(currentBranchIndex, ((BakedFunctionTree)tree).code);
-        //code[0] = code[0] + 1;
-
-        throw new NotImplementedException();
-      }
+      if(!treesExpanded) throw new InvalidOperationException();
+      subTrees.Insert(index, tree);
     }
 
     public void RemoveSubTree(int index) {
-      if(treesExpanded) {
-        subTrees.RemoveAt(index);
-      } else {
-        //int nLocalVariables = (int)code[2];
-        //// skip branches
-        //int currentBranchIndex = 3 + nLocalVariables;
-        //for(int i = 0; i < index; i++) {
-        //  int branchLength = BranchLength(currentBranchIndex);
-        //  currentBranchIndex += branchLength;
-        //}
-        //int deletedBranchLength = BranchLength(currentBranchIndex);
-        //code.RemoveRange(currentBranchIndex, deletedBranchLength);
-        //code[0] = code[0] - 1;
-        throw new NotImplementedException();
-      }
+      // sanity check
+      if(!treesExpanded) throw new InvalidOperationException();
+      subTrees.RemoveAt(index);
     }
 
     private int PC;
-    private double[] codeArr;
+    private int DP;
+    private int[] codeArr;
+    private double[] dataArr;
+    private Dataset dataset;
+    private int sampleIndex;
     public double Evaluate(Dataset dataset, int sampleIndex) {
       PC = 0;
+      DP = 0;
       FlattenVariables();
       FlattenTrees();
       if(codeArr == null) {
-        codeArr = new double[code.Count];
+        codeArr = new int[code.Count];
+        dataArr = new double[data.Count];
         code.CopyTo(codeArr);
-      }
-      return EvaluateBakedCode(dataset, sampleIndex);
-    }
-
-    private double EvaluateBakedCode(Dataset dataset, int sampleIndex) {
-      double arity = codeArr[PC++];
-      double functionSymbol = codeArr[PC++];
-      double nLocalVariables = codeArr[PC++];
-      if(functionSymbol == variableSymbol) {
-        int var = (int)codeArr[PC++];
-        double weight = codeArr[PC++];
-        int offset = (int)codeArr[PC++];
-        return weight * dataset.GetValue(sampleIndex+offset, var);
-      } else if(functionSymbol == constantSymbol) {
-        double value = codeArr[PC++];
-        return value;
-      } else if(functionSymbol == additionSymbol) {
-        double sum = 0.0;
-        for(int i = 0; i < arity; i++) {
-          sum += EvaluateBakedCode(dataset, sampleIndex);
-        }
-        return sum;
-      } else if(functionSymbol == substractionSymbol) {
-        if(arity == 1) {
-          return -EvaluateBakedCode(dataset, sampleIndex);
-        } else {
-          double result = EvaluateBakedCode(dataset, sampleIndex);
-          for(int i = 1; i < arity; i++) {
-            result -= EvaluateBakedCode(dataset, sampleIndex);
-          }
-          return result;
-        }
-      } else if(functionSymbol == multiplicationSymbol) {
-        double result = 1.0;
-        for(int i = 0; i < arity; i++) {
-          result *= EvaluateBakedCode(dataset, sampleIndex);
-        }
-        return result;
-      } else if(functionSymbol == divisionSymbol) {
-        if(arity == 1) {
-          double divisor = EvaluateBakedCode(dataset, sampleIndex);
-          if(divisor == 0) return 0;
-          else return 1.0 / divisor;
-        } else {
-          double result = EvaluateBakedCode(dataset, sampleIndex);
-          for(int i = 1; i < arity; i++) {
-            double divisor = EvaluateBakedCode(dataset, sampleIndex);
-            if(divisor == 0) result = 0; 
-            else result /= divisor;
-          }
-          return result;
-        }
-      } else { throw new NotSupportedException(); }
+        data.CopyTo(dataArr);
+      }
+      this.sampleIndex = sampleIndex;
+      this.dataset = dataset;
+      return EvaluateBakedCode();
+    }
+
+    private double EvaluateBakedCode() {
+      int arity = codeArr[PC++];
+      int functionSymbol = codeArr[PC++];
+      int nLocalVariables = codeArr[PC++];
+      switch(functionSymbol) {
+        case VARIABLE: {
+            int var = (int)dataArr[DP++];
+            double weight = dataArr[DP++];
+            int offset = (int)dataArr[DP++];
+            return weight * dataset.GetValue(sampleIndex + offset, var);
+          }
+        case CONSTANT: {
+            double value = dataArr[DP++];
+            return value;
+          }
+        case MULTIPLICATION: {
+            double result = 1.0;
+            for(int i = 0; i < arity; i++) {
+              result *= EvaluateBakedCode();
+            }
+            return result;
+          }
+        case ADDITION: {
+            double sum = 0.0;
+            for(int i = 0; i < arity; i++) {
+              sum += EvaluateBakedCode();
+            }
+            return sum;
+          }
+        case SUBSTRACTION: {
+            if(arity == 1) {
+              return -EvaluateBakedCode();
+            } else {
+              double result = EvaluateBakedCode();
+              for(int i = 1; i < arity; i++) {
+                result -= EvaluateBakedCode();
+              }
+              return result;
+            }
+          }
+        case DIVISION: {
+            if(arity == 1) {
+              double divisor = EvaluateBakedCode();
+              if(divisor == 0) return 0;
+              else return 1.0 / divisor;
+            } else {
+              double result = EvaluateBakedCode();
+              for(int i = 1; i < arity; i++) {
+                double divisor = EvaluateBakedCode();
+                if(divisor == 0) result = 0;
+                else result /= divisor;
+              }
+              return result;
+            }
+          }
+        case AVERAGE: {
+            double sum = 0.0;
+            for(int i = 0; i < arity; i++) {
+              sum += EvaluateBakedCode();
+            }
+            return sum / arity;
+          }
+        case COSINUS: {
+            return Math.Cos(EvaluateBakedCode());
+          }
+        case SINUS: {
+            return Math.Sin(EvaluateBakedCode());
+          }
+        case EXP: {
+            return Math.Exp(EvaluateBakedCode());
+          }
+        case LOG: {
+            return Math.Log(EvaluateBakedCode());
+          }
+        case POWER: {
+            double x = EvaluateBakedCode();
+            double p = EvaluateBakedCode();
+            return Math.Pow(x, p);
+          }
+        case SIGNUM: {
+            // protected signum
+            double value = EvaluateBakedCode();
+            if(value < 0) return -1;
+            if(value > 0) return 1;
+            return 0;
+          }
+        case SQRT: {
+            return Math.Sqrt(EvaluateBakedCode());
+          }
+        case TANGENS: {
+            return Math.Tan(EvaluateBakedCode());
+          }
+        case AND: {
+            double result = 1.0;
+            // have to evaluate all sub-trees, skipping would probably not lead to a big gain because 
+            // we have to iterate over the linear structure anyway
+            for(int i = 0; i < arity; i++) {
+              double x = Math.Round(EvaluateBakedCode());
+              if(x == 0) result *= 0;
+              else if(x == 1.0) result *= 1.0;
+              else result *= double.NaN;
+            }
+            return result;
+          }
+        case EQU: {
+            double x = EvaluateBakedCode();
+            double y = EvaluateBakedCode();
+            if(x == y) return 1.0; else return 0.0;
+          }
+        case GT: {
+            double x = EvaluateBakedCode();
+            double y = EvaluateBakedCode();
+            if(x > y) return 1.0;
+            else return 0.0;
+          }
+        case IFTE: {
+            double condition = Math.Round(EvaluateBakedCode());
+            double x = EvaluateBakedCode();
+            double y = EvaluateBakedCode();
+            if(condition < .5) return x;
+            else if(condition >= .5) return y;
+            else return double.NaN;
+          }
+        case LT: {
+            double x = EvaluateBakedCode();
+            double y = EvaluateBakedCode();
+            if(x < y) return 1.0;
+            else return 0.0;
+          }
+        case NOT: {
+            double result = Math.Round(EvaluateBakedCode());
+            if(result == 0.0) return 1.0;
+            else if(result == 1.0) return 0.0;
+            else return double.NaN;
+          }
+        case OR: {
+            double result = 0.0; // default is false
+            for(int i = 0; i < arity; i++) {
+              double x = Math.Round(EvaluateBakedCode());
+              if(x == 1.0 && result == 0.0) result = 1.0; // found first true (1.0) => set to true
+              else if(x != 0.0) result = double.NaN; // if it was not true it can only be false (0.0) all other cases are undefined => (NaN)
+            }
+            return result;
+          }
+        case XOR: {
+            double x = Math.Round(EvaluateBakedCode());
+            double y = Math.Round(EvaluateBakedCode());
+            if(x == 0.0 && y == 0.0) return 0.0;
+            if(x == 1.0 && y == 0.0) return 1.0;
+            if(x == 0.0 && y == 1.0) return 1.0;
+            if(x == 1.0 && y == 1.0) return 0.0;
+            return double.NaN;
+          }
+        default: {
+            IFunction function = symbolTable[functionSymbol];
+            double[] args = new double[nLocalVariables + arity];
+            for(int i = 0; i < nLocalVariables; i++) {
+              args[i] = dataArr[DP++];
+            }
+            for(int j = 0; j < arity; j++) {
+              args[nLocalVariables + j] = EvaluateBakedCode();
+            }
+            return function.Apply(dataset, sampleIndex, args);
+          }
+      }
     }
 
@@ -343 +489 @@
     public override object Clone(IDictionary<Guid, object> clonedObjects) {
       BakedFunctionTree clone = new BakedFunctionTree();
-      if(treesExpanded || variablesExpanded) throw new InvalidOperationException();
-      //if(treesExpanded) FlattenTrees();
-      //if(variablesExpanded) FlattenVariables();
-      clone.code = new List<double>(code);
+      if(treesExpanded || variablesExpanded) throw new InvalidOperationException(); // sanity check
+      clone.code.AddRange(code);
+      clone.data.AddRange(data);
       return clone;
+    }
+
+    public override IView CreateView() {
+      return new FunctionTreeView(this);
     }
   }