0

我已经编写了自己的数学解析器,由于某种原因,当我尝试分析解析器时,它需要越来越多的时间来解析。

为了测试我使用了这个输入: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,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);
    }
}
4

1 回答 1

3

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

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

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

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

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

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

于 2013-06-29T13:13:58.963 回答