Java : Optimize loop of loop with a lot of semi-constant flags checking?

Question

I have a simple nested structure like this. (This is simplified version of real problem. Some of them actually use Hash_Set. )

class A{  AF a_field; B[] bs;}
class B{  BF b_field; C[] cs;}
class C{  CF c_field; D[] ds;}
class D{  DF d_field; }
static A[] as;  // loosely speaking, it has about 4000 D

A psuedo-code method "f" may seem to be complex but it is really easy to understand :-

int f(int TYPE){ //TYPE is 0 - 40 
    int retur=0;
    for(int n=0;n<as.length;n++){
    .   if(some cheap condition of TYPE){ //use only "TYPE" , cheap (1)
    .   .   as[n].a_field.doExpensiveAA(); //expensive OPERATION, use only "a_field" (Ex retur+=a_field) 
    .   }else if(some cheap condition of TYPE){ //use only "TYPE" (2)
    .   .   as[n].a_field.doExpensiveAB(); //expensive OPERATION, use only "a_field" (Ex retur-=a_field)
    .   } // .... and a lot of them
    .   for(int m=0;m<bs.length;m++){
    .   .   if(some cheap condition of TYPE){ //use only "TYPE" (3)
    .   .   .   as[n].bs[m].b_field.doExpensiveBA(); (*)//use only "b_field" 
    .   .   }else if(some cheap condition of TYPE){//use only "TYPE" (4)
    .   .   .   as[n].bs[m].b_field.doExpensiveBB(); (/) //use only "b_field"
    .   .   } // .... and a lot of them
    .   .   for( ..cs .. ){...for(...ds...) {...}...} 
    .   }
    }
}

(I desperately add . for indentation.)

"f" is called in every time step :-

public static void caller (){
    for(int n=0;n<40;n++){ f(n); }
}

Notice that TYPE is only variable used in condition checking, and it is constant for a single "f" call.

Although each condition checking is really cheap but when it is in the innermost loop, it costs a lot CPU cycles. How to optimize "caller" and/or "f"?

My idea is to

1. unwrap "f" for each "TYPE" , but there will be a lot of dirty code that is hard to maintain ... like this...

   public static void caller (){ f1();f2();f3(); ... f40(); }

2. Use switch case! It is faster than if-else but switch-case 0 to 40 is ugly. The condition cannot be group like "checking odd/even of TYPE" anymore, so lower maintainability of code.

Edit 1 (answer Partha Sarathi Ghosh): the checking bit is just example ,so index of bit is unimportant, it can be even "> 8", just to note that all condition is depend on TYPE.

Edit 2 : The + - * / is just example, it is an arbitrary function that use the a_field,b_field, etc. (Real case is setting 3D texture or system variables in Opengl) ...cs... and ...ds... is the similar but different expensive operation.

Edit 3 : add information that "A[] as" contains about 4000 D

Edit 4 (answer Partha Sarathi Ghosh): Edit xxx_field's type from int to show they are different Class.

Answer 1

You need to pass a function as a parameter to a recursive function. See this post in while I prepare you basic algorithm.

You also need to use your custom Marker interface to pass those different type of data in same recursive method.

Here is your sample program.

import java.util.List;
import java.util.ArrayList;



/** The Invoker class */
class Switch {
    List<Command> commandList = new ArrayList<Command>();
    Switch() {
        commandList.add(new IncreementCommand()); //Level 1 Operation
        commandList.add(new MultipleCommand());
        commandList.add(new DecrementCommand());
        //If level 4 need same operation like level 1
        commandList.add(new IncreementCommand()); 

    }

    public int execute(CustomMarker a, int lvl){
        int rtr = 0;
        Command cmd = commandList.get(lvl-1); //Level 1 means 1st operation
        return execute(a, lvl, rtr, cmd);
    }


    /** The Command interface */
    interface Command {
        int execute(int data, int rtr);
    }

   private int execute(CustomMarker a, int lvl, int rtr, Command cmd){
       if(lvl == 0){
           return cmd.execute(a.getData(), rtr);
       }
       else {
           lvl--;
           if(a.getSubData() != null && a.getSubData().length>0){
               for (int i = 0; i < a.getSubData().length; i++) {
                 rtr = execute(a.getSubData()[i], lvl, rtr, cmd);
               }
           }
           return rtr;
       }
   }

   //Inner classes
   class IncreementCommand implements Command {
       @Override    // Command
       public int execute(int data, int rtr) {
          return rtr+data;
       }
    }

    /** The Command for turning off the light - ConcreteCommand #2 */
    class MultipleCommand implements Command {
        @Override    // Command
        public int execute(int data, int rtr) {
           return rtr*data;
        }
    }

    /** The Command for turning off the light - ConcreteCommand #2 */
    class DecrementCommand implements Command {
        @Override    // Command
        public int execute(int data, int rtr) {
           return rtr-data;
        }
    }
}

/** The Custom Marker interface */
interface CustomMarker {
    //It will return your int a_field or b_field
   public int getData();
   public CustomMarker[] getSubData();
}


//Level 1
class A implements CustomMarker {  int a_field; B[] bs;
    public int getData() {
        return a_field;
    }
    public CustomMarker[] getSubData() {
        return bs;
    }
}
//Level 2
class B implements CustomMarker {  int b_field; C[] cs;
    public int getData() {
        return b_field;
    }
    public CustomMarker[] getSubData() {
        return cs;
    }
}
//Level 3
class C implements CustomMarker {  int c_field; D[] ds;
    public int getData() {
        return c_field;
    }
    public CustomMarker[] getSubData() {
        return ds;
    }
}
//Level 4
class D implements CustomMarker {  int d_field; 
    public int getData() {
        return d_field;
    }
    public CustomMarker[] getSubData() {
        return null;
    }
}


/* The test class or client */
public class TestClass {
   static A[] as;
   public static void main(String[] args){



      CustomMarker topLevel = new CustomMarker() {
        @Override
        public int getData() {
            // TODO Auto-generated method stub
            return 0;
        }
        @Override
        public CustomMarker[] getSubData() {
            return as;
        }
      };

      Switch mySwitch = new Switch();
      for(int n=1;n<=3;n++){ 
          mySwitch.execute(topLevel, n); 
      }
   }
}

In this program I have used same data type for a_field and b_field as int. But you can try it with Object. So in each operation execute block typecast it. You do not need to check before typecast if your program can properly handle the level and its type.

I have minimized new operation to 41 times only. 40 operation and + 1 switch (Operation controller).

EDIT: Updated the execute public method of Switch class, copy pasted mistake was there.