java - 関数を繰り返す時間が指数関数的に増加する

Question

独自の数学パーサーを作成しましたが、何らかの理由で、パーサーのプロファイルを作成しようとすると、解析に時間がかかります。

テストでは、次の入力を使用しました。Cmd.NUM_9,Cmd.NUM_0,Cmd.NUM_0,Cmd.DIV,Cmd.NUM_2,Cmd.ADD,Cmd.NUM_6,Cmd.MULT,Cmd.NUM_3

1 回の実行 ~1.7ms
3000 回の繰り返し ~1,360ms
6000 回の繰り返し ~5,290ms
9000 回の繰り返し ~11,800ms

プロファイラーによると、時間の 64% がこの関数に費やされました。これは、暗黙的な乗算を可能にするための関数です。

private void enableImplicitMultiplication(ArrayList<Cmd> input) {
    int input_size = input.size();
    if (input_size<2) return;
    for (int i=0; i<input_size; i++) {
        Cmd cmd = input.get(i);
        if (i>0) {
            Cmd last = input.get(i-1);
            // [EXPR1, EXPR2] => [EXPR1, MULT, EXPR2]
            boolean criteria1 = Cmd.exprnCmds.contains(cmd) && Cmd.exprnCmds.contains(last);
            // [CBRAC, OBRAC] => [CBRAC, MULT, OBRAC]
            // [NUM_X, OBRAC] => [NUM_X, MULT, OBRAC]
            boolean criteria2 = cmd==Cmd.OBRAC && (last==Cmd.CBRAC || Cmd.constantCmds.contains(last));
            // [CBRAC, NUM_X] => [CBRAC, MULT, NUM_X]
            boolean criteria3 = last==Cmd.CBRAC && Cmd.constantCmds.contains(cmd);
            if (criteria1 || criteria2 || criteria3) {
                input.add(i++, Cmd.MULT);
            }
        }
    }
}

何が起きてる？？

私は次のように繰り返しを実行しました：

public static void main(String[] args) {
    Cmd[] iArray = {
        Cmd.NUM_9,Cmd.NUM_0,Cmd.NUM_0,Cmd.DIV,Cmd.NUM_2,Cmd.ADD,Cmd.NUM_6,Cmd.MULT,Cmd.NUM_3
    };
    ArrayList<Cmd> inputArray = new ArrayList<Cmd>(Arrays.asList(iArray));
    DirtyExpressionParser parser = null;
    int repeat=9000;
    double starttime = System.nanoTime();
    for (int i=0; i<repeat; i++) {
         parser = new DirtyExpressionParser(inputArray);
    }
    double endtime = System.nanoTime();
    System.out.printf("Duration: %.2f ms%n",(endtime-starttime)/1000000);
    System.out.println(parser.getResult());
}

コンストラクタは次のようになります。

public DirtyExpressionParser(ArrayList<Cmd> inputArray) {
    enableImplicitMultiplication(inputArray); //executed once for each repeat
    splitOnBrackets(inputArray); //resolves inputArray into Expr objects for each bracket-group
    for (Expr expr:exprArray) {
        mergeAndSolve(expr);
    }
}