java - String.replaceFirst 性能与算法替换

Question

假设我想用“zzz”替换字符串中第一次出现的“yyy”。 String.replaceFirst 似乎是一个完美的解决方案

str = str.repaceFirst("yyy", "zzz");

但是有性能问题吗？以下解决方案在性能方面有什么不同吗？

int i = s.indexOf("yyy");
if (i != -1) {
    str = str.substring(0, i) + "zzz" + s.substring(i + 3);
}

Answer 1

我写了some code来测试性能。请使用适当的参数在您的盒子上运行它以进行测试。命令行接受 0 到 1 之间的 double，表示插入 "yyy" 子字符串的测试输入的比率。

方法论

生成

5000个随机字符串，长度为50、100、500、1000等。 5000 个字符串中的一定比例会在随机位置插入序列“yyy”。 (由于生成方法的原因，字符串将仅包含 "yyy" 的单个实例(如果有的话)，但我认为这不是问题)。对于(字符串长度)和(方法)的每种组合，我运行测试 30 次并取平均值。

测试了以下 3 种方法:

1. 替换第一个:

   public static String replaceFirstApproach(String input) {
       return input.replaceFirst("yyy", "zzz");
   }
   

2. 子字符串:

   public static String substringApproach(String input) {
       int i = input.indexOf("yyy");
   
       if (i != -1) {
           input = input.substring(0, i) + "zzz" + input.substring(i + 3);
       }
   
       return input;
   }
   

3. 使用StringBuilder构造输出字符串:

   public static String appendStringBuilder(String input) {
       int i = input.indexOf("yyy");
   
       if (i != -1) {
           StringBuilder output = new StringBuilder(input.length());
           output.append(input, 0, i).append("zzz").append(input, i + 3, input.length());
           return output.toString();
       } else {
           return input;
       }
   }
   

结果

该程序在 JVM 7、Windows 7 上运行。这些数字是在微秒内处理一批 5000 个随机字符串的平均时间。

插入子字符串“yyy”的0%处

       Length |      50        100        500        1000         5000--------------|------------------------------------------------------- replaceFirst |   17389      22718      74194      137285       629438    substring |    4429       7246      13421       18069        78920StringBuilder |    4604       5615      11509       19093        79366

插入子字符串“yyy”的25%处

       Length |      50        100        500        1000         5000--------------|------------------------------------------------------- replaceFirst |   18531      24959      78211      146956       692992    substring |    5250       6764      18994       27959       113805StringBuilder |    5768       8609      23857       45789       205580

插入子字符串“yyy”的50%处

       Length |      50        100        500        1000         5000--------------|------------------------------------------------------- replaceFirst |   19833      27648      90932      162558       760558    substring |    6007       8848      21909       37415       154959StringBuilder |    7075      12095      37765       70038       327171

插入子字符串“yyy”的75%处

       Length |      50        100        500        1000         5000--------------|------------------------------------------------------- replaceFirst |   20318      28387      95967      176051       845799    substring |    6840       9940      27469       47218       198464StringBuilder |    8794      13272      50498       94644       470656

插入子字符串“yyy”的100%处

       Length |      50        100        500        1000         5000--------------|------------------------------------------------------- replaceFirst |   22984      31302     103640      192179       892965    substring |    7846      11494      37093       58544       258356StringBuilder |   11113      24499      66164      121784       592664

结论

使用replaceFirst的方法总是最慢的。当"yyy"子串没有找到时，它比其他2种方法慢3-10倍。当可以找到"yyy"子串时，仍然比substring方法慢3倍，比StringBuilder方法慢1.5倍。

当“yyy”时，使用+和substring连接字符串的方法比StringBuilder快2倍可以找到子串，而且字符串很长。

不过，这里的用例是相当本地化的。尽管substring 方法速度更快，但除非您进行密集的字符串处理，否则 yield 微不足道。