java - Java 中 String.replaceFirst ("^...") 的预期运行时间是多少

Question

假设我有一个非常长字符串str = "abcdef..."。

我想使用 str.replaceFirst("^xyz","") 替换其中可能的 "xyz" 前缀。

上述表达式的预期运行时间是多少？

replaceFirst 会在第一个字符之后立即返回，还是会迭代整个字符串？

P.S.:我需要一个知道 Java 字节码解释器在编译(或者我应该说“解释”) 的 replaceFirst 方法时如何在幕后工作的人的答案。 String 类。

更新:

无论为了返回结果而创建的中间字符串如何，请考虑我的问题。在任何情况下都会发生这种情况(无论我使用什么 String 方法来完成所需的转换)。因此，我删除了涉及复杂性的部分，因为无论如何它都是 O(n)...

总结一下问题:

我可以假设正则表达式匹配本身的运行时间不依赖于str的长度吗？

Answer 1

replaceFirst 在我的 jdk 版本上使用 StringBuffer 创建一个新字符串。因此，假设正则表达式和替换字符串的长度都很小，由于字符串复制，其时间复杂度为 O(n)，其中 n 是初始字符串的长度:

public String replaceFirst(String replacement) {
    if (replacement == null)
        throw new NullPointerException("replacement");
    reset();
    if (!find())
        return text.toString();
    StringBuffer sb = new StringBuffer();
    appendReplacement(sb, replacement);
    appendTail(sb);
    return sb.toString();
}

注释:

• 正则表达式匹配本身应该是 O(1)。
• 如果没有匹配，则replaceFirst转到return text.toString()，它返回字符串本身:如果没有匹配，则它是O(1) 运算。
• startsWith + substring 曾经是 O(1)(当 substring 是字符串的 View 时，即直到 Java 7u5)，但是现在也是 O(n)(因为 Java 7y6 substring 通过复制底层 char 数组创建一个新字符串)。

<小时/>

更新

我快速测试了操作的性能，通过使用 ^ anchor 和不使用 anchor 的正则表达式来匹配空字符串和长字符串，以确认上述情况。结果(每次调用以纳秒为单位):

p1s1 (empty string, "^x")   47.561 nsec/op
p1s2 (long string, "^x")    50.753 nsec/op
p2s1 (empty string, "x")    47.526 nsec/op
p2s2 (long string, "x")    131.015 nsec/op

因此您可以看到 "^x" 正则表达式会删除第一个字符处的分析，因为时间(几乎)与空字符串或长字符串相同。

代码，使用 jmh 进行 benhcmarking:

private String s1 = "";
private String s2 = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" +
                    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" +
                    "x";
private static final Pattern p1 = Pattern.compile("^x");
private static final Pattern p2 = Pattern.compile("x");

@GenerateMicroBenchmark
public boolean p1s1() { return p1.matcher(s1).find(); }

@GenerateMicroBenchmark
public boolean p1s2() { return p1.matcher(s2).find(); }

@GenerateMicroBenchmark
public boolean p2s1() { return p2.matcher(s1).find(); }

@GenerateMicroBenchmark
public boolean p2s2() { return p2.matcher(s2).find(); }