java - 我应该改变什么来优化替换方法？

Question

我正在创建一个方法来了解字符串中有多少次“RAV”。我的程序可以运行，但当字符串有 +10.000 个字符时，它应该更快。

首先我使用 String，然后使用 StringBuilder，它速度更快，但还不够。

public class E{

    private static int replace(String cad){
        StringBuilder sb = new StringBuilder(cad);
        int cont = 0;
        while (sb.indexOf("RAV") > -1 && cont < 50000) {
            sb.replace(sb.indexOf("RAV"), sb.indexOf("RAV") + 3, "");
            cont++;
        }
        return cont;
    }
    public static void main(String[] args) {
        String[] arr = new String[]{"RARAVV", "VAR", "RAVV"};
        for (int i = 0; i < arr.length; i++) {
            System.out.println(replace(arr[i]));
        }
    }
}

预期输出是

2
0
1

Answer 1

private static int replace(String cad) {
    int originalLength = cad.length();
    for (;;) {
        String cad2 = cad.replace("RAV", "");
        if (cad2.length() == cad.length()) {
            break;
        }
        cad = cad2;
    }
    return (originalLength - cad.length()) / "RAV".length();
}

首先，indexOf应该放入一个变量中，作为三次使用。String.replace 可以进行多次替换。然后，表达式缩减具有不同的顺序，但对于“RAV”，不会产生不同的结果。

在上面，您可以测试 cad2 == cad 的替换结果，但某些样式检查器会更喜欢等于。长度相等就足够了。

当然替换的次数就是长度减少/3。

<小时/>

实际测量显示 String.replace(String, String) 速度很慢:

private static int replace(String cad) {
    // Could try to shorten string: cad = cad.replaceAll("[^RAV]+", "e");
    StringBuilder sb = new StringBuilder(cad);
    int pos0 = 0;
    for (;;) {
        int pos = sb.indexOf("RAV", pos0);
        if (pos == -1) {
            break;
        }
        sb.delete(pos, pos + 3);
        // Continue searching 2 chars before.
        pos0 = Math.max(0, pos - 2); // RA[RAV]V
    }
    return (cad.length() - sb.length()) / 3;
}

感谢@GPI 的基准测试。