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

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

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

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

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

P.S .：我需要一个知道Java字节码解释器在编译（或称“解释”）replaceFirst类的String方法时如何在后台工作的人的答案。

更新：

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

所以总结一下问题：

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

最佳答案

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是字符串视图时，即直到Java 7u5），但现在也是O（n）（因为Java 7y6 substring创建了新字符串）通过复制底层的char数组）。




更新资料

我已经通过使用^锚匹配一个空字符串和一个长字符串与一个正则表达式来快速测试该操作的性能，以确认以上内容，并使用一个不包含它的锚。结果（每个呼叫以纳秒为单位）：

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(); }