Faster way to split a string in java then add to an ArrayList

Question

For a school project I was asked to write a simple math parser in Java. The program works fine. So fine that I used NetBeans profiler tool to check the performance of the program. For that I made a loop of 1000 calls to the math parser of the following expression: "1-((x+1)+1)*2", where x was replaced by the current loop count. It took 262ms. The thing is, it took 50% of the time in the method splitFormula, which I shall present below:

private static void splitFormula(String formula){
    partialFormula=new ArrayList<>();

    for(String temp: formula.split("\\+|\\-|\\*|\\/"))
        partialFormula.add(temp);
}

, where partialFormula is an ArrayList of Strings. To numerically evaluate an expression I need to call the splitFormula method various times so I really need to clear the contents of the partialFormula ArrayList - first line.

My question is: is there a faster way to split a string then add the partial strings to the an arraylist? Or is there some other method that can be used to split a string then use the substrings?

Answer 1

Regular expressions can slow things down (String#split uses regex). In general, if you want to write easy code, regex is good, but if you want fast code, see if there is another way. Try doing this without regex:

Edit: This should be a better method (keep track of the indices instead of append to a StringBuilder):

private static void splitFormula(String formula){
    partialFormula.clear(); // since there is a method for this, why not use it?

    int lastIndex = 0;
    for (int index = 0; index < formula.length(); index++) {
        char c = formula.charAt(index);
        if (c == '-' || c == '+' || c == '*' || c == '/') {
            partialFormula.add(formula.substring(lastIndex, index));
            lastIndex = index + 1; //because if it were index, it would include the operator
        }
    }
    partialFormula.add(formula.substring(lastIndex));
}

StringBuilder approach:

private static void splitFormula(String formula){
    partialFormula.clear();

    StringBuilder newStr = new StringBuilder();

    for (int index = 0; index < formula.length(); index++) {
        char c = formula.charAt(index);
        if (c == '-' || c == '+' || c == '*' || c == '/') {
            partialFormula.add(newStr.toString());
            newStr.setLength(0);
        } else {
            newStr.append(c);
        }
    }
    partialFormula.add(newStr.toString());
}

---

If we look at the source code for String#split, it becomes apparent why that is slower (from GrepCode):

public String[] split(String regex, int limit) {
    return Pattern.compile(regex).split(this, limit);
}

It compiles a regex every time! Thus, we can see that another way of speeding up the code is to compile our regex first, then use the Pattern#split to split:

//In constructor, or as a static variable.
//This regex is a better form of yours.
Pattern operatorPattern = Pattern.compile("[-*+/]");
...
private static void splitFormula(String formula){
    partialFormula.clear();

    for(String temp: operatorPattern.split(formula)) {
        partialFormula.add(temp);
    }
}