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

Question

我有一个像这样的简单嵌套结构。 (这是真实问题的简化版，其中一些实际上使用了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

一个伪代码方法“f”可能看起来很复杂，但它真的很容易理解:-

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...) {...}...} 
    .   }
    }
}

(我拼命添加 . 用于缩进。)

“f”在每个时间步被调用:-

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

请注意，TYPE 只是用于条件检查的变量，对于单个“f”调用而言它是常量。

虽然每个条件检查确实很便宜，但是当它在最内层循环时，它会消耗很多 CPU 周期。如何优化“caller”和/或“f”？

我的想法是

1. 为每个“TYPE”解包“f”，但是会有很多难以维护的脏代码……像这样……

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

2. 使用开关盒!它比 if-else 快，但 switch-case 0 到 40 很难看。条件不能像“检查TYPE的奇数/偶数”那样分组，因此代码的可维护性较低。

编辑 1(回答 Partha Sarathi Ghosh):检查位只是示例，因此位索引并不重要，它甚至可以是“> 8”，只是要注意所有条件都取决于在类型上。

Edit 2 : + - */只是例子，它是一个使用a_field,b_field等的任意函数(实际情况是在Opengl中设置3D纹理或系统变量)。 ..cs... 和 ...ds... 是相似但不同的昂贵操作。

编辑3:添加信息“A[] as”包含大约4000 D

编辑 4(回答 Partha Sarathi Ghosh):将 xxx_field 的类型从 int 编辑为显示它们是不同的类。

Answer 1

您需要将函数作为参数传递给递归函数。看这个post在我为您准备基本算法的同时。

您还需要使用自定义标记接口(interface)以相同的递归方法传递那些不同类型的数据。

这是您的示例程序。

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); 
      }
   }
}

在这个程序中，我为 a_field 和 b_field 使用了与 int 相同的数据类型。但是你可以用 Object.所以在每个操作中执行 block 类型转换它。如果您的程序可以正确处理关卡及其类型，则无需在类型转换之前进行检查。

我已将 new 操作最小化到仅 41 次。 40个操作+1个开关(操作 Controller )。

编辑:更新了Switch类的execute public方法，复制粘贴错误。