Changeset 328 for branches

Timestamp:

06/20/08 18:12:20 (16 years ago)

Author:

gkronber

Message:

more work on GP evaluation - work in progress - bug nest

Location:

branches/BottomUpTreeEvaluation

Files:

• BakedTreeEvaluator.cs (modified) (8 diffs)
• SymbolTable.cs (modified) (1 diff)

branches/BottomUpTreeEvaluation/BakedTreeEvaluator.cs

@@ -33 +33 @@
     private const int MAX_TREE_DEPTH = 20;
     private class Instr {
+      public double result;
       public double d_arg0;
       public int i_arg0;
@@ -59 +60 @@
       int length;
       for(int i = 0; i < MAX_TREE_DEPTH; i++) nInstr[i] = 0;
-      TranslateToInstr(0, linearRepresentation, out length);
-    }
-
-    private static int TranslateToInstr(int pos, List<LightWeightFunction> linearRepresentation, out int branchLength) {
+      //TranslateToInstr(0, linearRepresentation, out length);
+      int[] heights = new int[linearRepresentation.Count];
+      CalcHeights(linearRepresentation, heights, 0, out length);
+      TranslateToTable(0, linearRepresentation, heights);
+    }
+
+    private static int CalcHeights(List<LightWeightFunction> linearRepresentation, int[] heights, int p, out int branchLength) {
+      if(linearRepresentation[p].arity == 0) {
+        heights[p] = 1;
+        branchLength = 1;
+        return 1;
+      }
       int height = 0;
       int length = 1;
-      LightWeightFunction f = linearRepresentation[pos];
-      for(int i = 0; i < f.arity; i++) {
+      for(int i = 0; i < linearRepresentation[p].arity; i++) {
         int curBranchLength;
-        int curBranchHeight = TranslateToInstr(pos + length, linearRepresentation, out curBranchLength);
-        if(curBranchHeight > height) height = curBranchHeight;
+        int curHeight = CalcHeights(linearRepresentation, heights, p + length, out curBranchLength);
+        if(curHeight > height) {
+          height = curHeight;
+        }
         length += curBranchLength;
       }
-      Instr instr = evaluationTable[nInstr[height], height];
-      instr.arity = f.arity;
-      instr.symbol = EvaluatorSymbolTable.MapFunction(f.functionType);
-      switch(instr.symbol) {
-        case EvaluatorSymbolTable.VARIABLE: {
-            instr.i_arg0 = (int)f.data[0]; // var
-            instr.d_arg0 = f.data[1]; // weight
-            instr.i_arg1 = (int)f.data[2]; // sample-offset
-            break;
+      heights[p] = height+1;
+      branchLength = length;
+      return height+1;
+    }
+
+    private static int TranslateToTable(int pos, List<LightWeightFunction> list, int[] heights) {
+      LightWeightFunction f = list[pos];
+      if(f.arity == 0) {
+        Instr instr = evaluationTable[nInstr[0], 0];
+        instr.symbol = EvaluatorSymbolTable.MapFunction(f.functionType);
+        switch(instr.symbol) {
+          case EvaluatorSymbolTable.VARIABLE: {
+              instr.i_arg0 = (int)f.data[0]; // var
+              instr.d_arg0 = f.data[1]; // weight
+              instr.i_arg1 = (int)f.data[2]; // sample-offset
+              break;
+            }
+          case EvaluatorSymbolTable.CONSTANT: {
+              instr.result = f.data[0]; // value
+              break;
+            }
+        }
+        nInstr[0]++;
+        return 1;
+      } else {
+        int length = 1;
+        int height = heights[pos];
+        for(int i = 0; i < f.arity; i++) {
+          int curBranchHeight = heights[pos + length];
+          if(curBranchHeight < height - 1) {
+            for(int j = curBranchHeight; j < height - 1; j++) {
+              evaluationTable[nInstr[j], j].symbol = EvaluatorSymbolTable.IDENTITY;
+              nInstr[j]++;
+            }
           }
-        case EvaluatorSymbolTable.CONSTANT: {
-            instr.d_arg0 = f.data[0]; // value
-            break;
-          }
-      }
-      nInstr[height]++;
-      branchLength = length;
-      return height;
-    }
-
-    //private static Instr TranslateToInstr(LightWeightFunction f, Instr instr) {
+          int curBranchLength = TranslateToTable(pos + length, list, heights);
+          length += curBranchLength;
+        }
+
+        Instr cell = evaluationTable[nInstr[height-1], height-1];
+        nInstr[height-1]++;
+        cell.arity = f.arity;
+        cell.symbol = EvaluatorSymbolTable.MapFunction(f.functionType);
+        return length;
+      }
+    }
+
+
+    //private static int TranslateToInstr(int pos, List<LightWeightFunction> linearRepresentation, out int branchLength) {
+    //  int height = 0;
+    //  int length = 1;
+    //  LightWeightFunction f = linearRepresentation[pos];
+    //  for(int i = 0; i < f.arity; i++) {
+    //    int curBranchLength;
+    //    int curBranchHeight = TranslateToInstr(pos + length, linearRepresentation, out curBranchLength);
+    //    if(curBranchHeight > height) height = curBranchHeight;
+    //    length += curBranchLength;
+    //  }
+    //  Instr instr = evaluationTable[nInstr[height], height];
     //  instr.arity = f.arity;
     //  instr.symbol = EvaluatorSymbolTable.MapFunction(f.functionType);
@@ -103 +151 @@
     //      }
     //    case EvaluatorSymbolTable.CONSTANT: {
-    //        instr.d_arg0 = f.data[0]; // value
+    //        instr.result = f.data[0]; // value
     //        break;
     //      }
     //  }
-    //  return instr;
+    //  nInstr[height]++;
+    //  branchLength = length;
+    //  return height + 1;
     //}
 
@@ -118 +168 @@
     private static double EvaluateTable() {
       int terminalP = 0;
-      for(; terminalP < nInstr[0]; terminalP += 2) {
+      // process remaining instr first
+      for(int i = 0; i < nInstr[0] % 4; i++) {
+        Instr curInstr = evaluationTable[terminalP++, 0];
+        if(curInstr.symbol == EvaluatorSymbolTable.VARIABLE) {
+          int row = sampleIndex + curInstr.i_arg1;
+          if(row < 0 || row >= dataset.Rows) curInstr.result = double.NaN;
+          else curInstr.result = curInstr.d_arg0 * dataset.GetValue(row, curInstr.i_arg0);
+        }
+      }
+      // unrolled loop
+      for(; terminalP < nInstr[0] - 4; terminalP += 4) {
         Instr curInstr0 = evaluationTable[terminalP, 0];
         Instr curInstr1 = evaluationTable[terminalP + 1, 0];
+        Instr curInstr2 = evaluationTable[terminalP + 2, 0];
+        Instr curInstr3 = evaluationTable[terminalP + 3, 0];
         if(curInstr0.symbol == EvaluatorSymbolTable.VARIABLE) {
           int row = sampleIndex + curInstr0.i_arg1;
-          if(row < 0 || row >= dataset.Rows) curInstr0.d_arg0 = double.NaN;
-          else curInstr0.d_arg0 = curInstr0.d_arg0 * dataset.GetValue(row, curInstr0.i_arg0);
+          if(row < 0 || row >= dataset.Rows) curInstr0.result = double.NaN;
+          else curInstr0.result = curInstr0.d_arg0 * dataset.GetValue(row, curInstr0.i_arg0);
         }
         if(curInstr1.symbol == EvaluatorSymbolTable.VARIABLE) {
           int row = sampleIndex + curInstr1.i_arg1;
-          if(row < 0 || row >= dataset.Rows) curInstr1.d_arg0 = double.NaN;
-          else curInstr1.d_arg0 = curInstr1.d_arg0 * dataset.GetValue(row, curInstr1.i_arg0);
+          if(row < 0 || row >= dataset.Rows) curInstr1.result = double.NaN;
+          else curInstr1.result = curInstr1.d_arg0 * dataset.GetValue(row, curInstr1.i_arg0);
+        }
+        if(curInstr2.symbol == EvaluatorSymbolTable.VARIABLE) {
+          int row = sampleIndex + curInstr2.i_arg1;
+          if(row < 0 || row >= dataset.Rows) curInstr2.result = double.NaN;
+          else curInstr2.result = curInstr2.d_arg0 * dataset.GetValue(row, curInstr2.i_arg0);
+        }
+        if(curInstr3.symbol == EvaluatorSymbolTable.VARIABLE) {
+          int row = sampleIndex + curInstr3.i_arg1;
+          if(row < 0 || row >= dataset.Rows) curInstr3.result = double.NaN;
+          else curInstr3.result = curInstr3.d_arg0 * dataset.GetValue(row, curInstr3.i_arg0);
         }
       }
@@ -140 +212 @@
           switch(curInstr.symbol) {
             case EvaluatorSymbolTable.MULTIPLICATION: {
-                curInstr.d_arg0 = evaluationTable[lastLayerInstrP, curLevel - 1].d_arg0;
+                curInstr.result = evaluationTable[lastLayerInstrP++, curLevel - 1].result;
                 for(int i = 1; i < curInstr.arity; i++) {
-                  curInstr.d_arg0 *= evaluationTable[lastLayerInstrP + i, curLevel - 1].d_arg0;
-                }
-                lastLayerInstrP += curInstr.arity;
+                  curInstr.result *= evaluationTable[lastLayerInstrP++, curLevel - 1].result;
+                }
                 break;
               }
             case EvaluatorSymbolTable.ADDITION: {
-                curInstr.d_arg0 = evaluationTable[lastLayerInstrP, curLevel - 1].d_arg0;
+                curInstr.result = evaluationTable[lastLayerInstrP++, curLevel - 1].result;
                 for(int i = 1; i < curInstr.arity; i++) {
-                  curInstr.d_arg0 += evaluationTable[lastLayerInstrP + i, curLevel - 1].d_arg0;
-                }
-                lastLayerInstrP += curInstr.arity;
+                  curInstr.result += evaluationTable[lastLayerInstrP++, curLevel - 1].result;
+                }
                 break;
               }
             case EvaluatorSymbolTable.SUBTRACTION: {
                 if(curInstr.arity == 1) {
-                  curInstr.d_arg0 = -evaluationTable[lastLayerInstrP++, curLevel - 1].d_arg0;
+                  curInstr.result = -evaluationTable[lastLayerInstrP++, curLevel - 1].result;
                 } else {
-                  curInstr.d_arg0 = evaluationTable[lastLayerInstrP, curLevel - 1].d_arg0;
+                  curInstr.result = evaluationTable[lastLayerInstrP++, curLevel - 1].result;
                   for(int i = 1; i < curInstr.arity; i++) {
-                    curInstr.d_arg0 -= evaluationTable[lastLayerInstrP + i, curLevel - 1].d_arg0;
+                    curInstr.result -= evaluationTable[lastLayerInstrP++, curLevel - 1].result;
                   }
-                  lastLayerInstrP += curInstr.arity;
                 }
                 break;
@@ -169 +238 @@
             case EvaluatorSymbolTable.DIVISION: {
                 if(curInstr.arity == 1) {
-                  curInstr.d_arg0 = 1.0 / evaluationTable[lastLayerInstrP++, curLevel - 1].d_arg0;
+                  curInstr.result = 1.0 / evaluationTable[lastLayerInstrP++, curLevel - 1].result;
                 } else {
-                  curInstr.d_arg0 = evaluationTable[lastLayerInstrP, curLevel - 1].d_arg0;
+                  curInstr.result = evaluationTable[lastLayerInstrP++, curLevel - 1].result;
                   for(int i = 1; i < curInstr.arity; i++) {
-                    curInstr.d_arg0 /= evaluationTable[lastLayerInstrP + i, curLevel - 1].d_arg0;
+                    curInstr.result /= evaluationTable[lastLayerInstrP++, curLevel - 1].result;
                   }
-                  lastLayerInstrP += curInstr.arity;
-                }
-                if(double.IsInfinity(curInstr.d_arg0)) curInstr.d_arg0 = 0.0;
+                }
+                if(double.IsInfinity(curInstr.result)) curInstr.result = 0.0;
                 break;
               }
             case EvaluatorSymbolTable.AVERAGE: {
-                curInstr.d_arg0 = evaluationTable[lastLayerInstrP, curLevel - 1].d_arg0;
+                curInstr.result = evaluationTable[lastLayerInstrP++, curLevel - 1].result;
                 for(int i = 1; i < curInstr.arity; i++) {
-                  curInstr.d_arg0 += evaluationTable[lastLayerInstrP + i, curLevel - 1].d_arg0;
-                }
-                lastLayerInstrP += curInstr.arity;
-                curInstr.d_arg0 /= curInstr.arity;
+                  curInstr.result += evaluationTable[lastLayerInstrP++, curLevel - 1].result;
+                }
+                curInstr.result /= curInstr.arity;
                 break;
               }
             case EvaluatorSymbolTable.COSINUS: {
-                curInstr.d_arg0 = Math.Cos(evaluationTable[lastLayerInstrP++, curLevel - 1].d_arg0);
+                curInstr.result = Math.Cos(evaluationTable[lastLayerInstrP++, curLevel - 1].result);
                 break;
               }
             case EvaluatorSymbolTable.SINUS: {
-                curInstr.d_arg0 = Math.Sin(evaluationTable[lastLayerInstrP++, curLevel - 1].d_arg0);
+                curInstr.result = Math.Sin(evaluationTable[lastLayerInstrP++, curLevel - 1].result);
                 break;
               }
             case EvaluatorSymbolTable.EXP: {
-                curInstr.d_arg0 = Math.Exp(evaluationTable[lastLayerInstrP++, curLevel - 1].d_arg0);
+                curInstr.result = Math.Exp(evaluationTable[lastLayerInstrP++, curLevel - 1].result);
                 break;
               }
             case EvaluatorSymbolTable.LOG: {
-                curInstr.d_arg0 = Math.Log(evaluationTable[lastLayerInstrP++, curLevel - 1].d_arg0);
+                curInstr.result = Math.Log(evaluationTable[lastLayerInstrP++, curLevel - 1].result);
                 break;
               }
             case EvaluatorSymbolTable.POWER: {
-                double x = evaluationTable[lastLayerInstrP++, curLevel - 1].d_arg0;
-                double p = evaluationTable[lastLayerInstrP++, curLevel - 1].d_arg0;
-                curInstr.d_arg0 = Math.Pow(x, p);
+                double x = evaluationTable[lastLayerInstrP++, curLevel - 1].result;
+                double p = evaluationTable[lastLayerInstrP++, curLevel - 1].result;
+                curInstr.result = Math.Pow(x, p);
                 break;
               }
             case EvaluatorSymbolTable.SIGNUM: {
-                double value = evaluationTable[lastLayerInstrP++, curLevel - 1].d_arg0;
-                if(double.IsNaN(value)) curInstr.d_arg0 = double.NaN;
-                else curInstr.d_arg0 = Math.Sign(value);
+                double value = evaluationTable[lastLayerInstrP++, curLevel - 1].result;
+                if(double.IsNaN(value)) curInstr.result = double.NaN;
+                else curInstr.result = Math.Sign(value);
                 break;
               }
             case EvaluatorSymbolTable.SQRT: {
-                curInstr.d_arg0 = Math.Sqrt(evaluationTable[lastLayerInstrP++, curLevel - 1].d_arg0);
+                curInstr.result = Math.Sqrt(evaluationTable[lastLayerInstrP++, curLevel - 1].result);
                 break;
               }
             case EvaluatorSymbolTable.TANGENS: {
-                curInstr.d_arg0 = Math.Tan(evaluationTable[lastLayerInstrP++, curLevel - 1].d_arg0);
+                curInstr.result = Math.Tan(evaluationTable[lastLayerInstrP++, curLevel - 1].result);
                 break;
               }
@@ -285 +352 @@
             //    return double.NaN;
             //  }
+            case EvaluatorSymbolTable.IDENTITY: {
+                curInstr.result = evaluationTable[lastLayerInstrP++, curLevel - 1].result;
+                break;
+              }
             default: {
                 throw new NotImplementedException();
@@ -290 +361 @@
           }
         }
-        // copy remaining results from previous layer to current layer (identiy function)
-        int r = 0;
-        for(; lastLayerInstrP < nInstr[curLevel - 1]; lastLayerInstrP++) {
-          evaluationTable[nInstr[curLevel] + r, curLevel].d_arg0 = evaluationTable[lastLayerInstrP, curLevel - 1].d_arg0;
-          r++;
-        }
         curLevel++;
       }
-      return evaluationTable[0, curLevel - 1].d_arg0;
+      return evaluationTable[0, curLevel - 1].result;
     }
   }

branches/BottomUpTreeEvaluation/SymbolTable.cs

@@ -52 +52 @@
     public const int VARIABLE = 22;
     public const int XOR = 23;
-    public const int UNKNOWN = 24;
+    public const int IDENTITY = 24;
+    public const int UNKNOWN = 25;
 
     private static Dictionary<Type, int> staticTypes = new Dictionary<Type,int>();