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.7ms
3000 次重复 ~ 1,360 毫秒
6000 次重复 ~ 5,290 毫秒
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);
    }
}

Answer 1

您的微基准测试代码完全错误:JVM 上的微基准测试本身就是一门手艺，最好留给专用工具，例如 jmh 或 Google Caliper。您不预热代码，不控制 GC 暂停，等等。

通过分析代码得出的一个细节是:

1. 您在函数调用的所有重复中重复使用相同的ArrayList；
2. 每个函数调用都可以向列表中插入一个元素；
3. 插入是 ArrayList 上的重量级操作:必须复制插入元素后列表的全部内容。

您至少应该为每次调用创建一个新的ArrayList，但这并不会使您的整个方法正确。

根据我们在评论中的讨论，我诊断出您在理解代码时可能遇到的以下问题:

在 Java 中，不存在值为对象的变量。变量的值是对象的引用。因此，当您说new DirtyExpressionParser(inputArray)时，构造函数不会收到自己的列表私有(private)副本，而是收到对唯一ArrayList的引用 您已在 main 方法中实例化。下一个构造函数调用将获取相同的列表，但现在已被先前的调用修改。这就是为什么您的列表一直在增长。