JVM String方法实现

Question

String类有一些方法,我无法理解为什么它们是这样实现的... replace是其中之一.

public String replace(CharSequence target, CharSequence replacement) {
    return Pattern.compile(target.toString(), Pattern.LITERAL).matcher(
            this).replaceAll(Matcher.quoteReplacement(replacement.toString()));
}

与更简单,更有效(快速!)的方法相比,是否有一些明显的优势？

public static String replace(String string, String searchFor, String replaceWith) {

    StringBuilder result=new StringBuilder();

    int index=0;
    int beginIndex=0;
    while((index=string.indexOf(searchFor, index))!=-1){
        result.append(string.substring(beginIndex, index)+replaceWith);
        index+=searchFor.length();
        beginIndex=index;
    }
    result.append(string.substring(beginIndex, string.length()));

    return result.toString();

}

使用Java 7的统计数据:
1,000,000次迭代
将"b"替换为"abc"
结果中的"x" :"axc"

时间:
string.replace:485ms
string.replaceAll:490ms
optimize replace = 180ms

像Java 7拆分方法这样的代码经过大量优化,以尽可能避免模式编译/正则表达式处理:

public String[] split(String regex, int limit) {
    /* fastpath if the regex is a
     (1)one-char String and this character is not one of the
        RegEx's meta characters ".$|()[{^?*+\\", or
     (2)two-char String and the first char is the backslash and
        the second is not the ascii digit or ascii letter.
     */
    char ch = 0;
    if (((regex.value.length == 1 &&
         ".$|()[{^?*+\\".indexOf(ch = regex.charAt(0)) == -1) ||
         (regex.length() == 2 &&
          regex.charAt(0) == '\\' &&
          (((ch = regex.charAt(1))-'0')|('9'-ch)) < 0 &&
          ((ch-'a')|('z'-ch)) < 0 &&
          ((ch-'A')|('Z'-ch)) < 0)) &&
        (ch < Character.MIN_HIGH_SURROGATE ||
         ch > Character.MAX_LOW_SURROGATE))
    {
        int off = 0;
        int next = 0;
        boolean limited = limit > 0;
        ArrayList<String> list = new ArrayList<>();
        while ((next = indexOf(ch, off)) != -1) {
            if (!limited || list.size() < limit - 1) {
                list.add(substring(off, next));
                off = next + 1;
            } else {    // last one
                //assert (list.size() == limit - 1);
                list.add(substring(off, value.length));
                off = value.length;
                break;
            }
        }
        // If no match was found, return this
        if (off == 0)
            return new String[]{this};

        // Add remaining segment
        if (!limited || list.size() < limit)
            list.add(substring(off, value.length));

        // Construct result
        int resultSize = list.size();
        if (limit == 0)
            while (resultSize > 0 && list.get(resultSize - 1).length() == 0)
                resultSize--;
        String[] result = new String[resultSize];
        return list.subList(0, resultSize).toArray(result);
    }
    return Pattern.compile(regex).split(this, limit);
}

遵循替换方法的逻辑:

public String replaceAll(String regex, String replacement) {
    return Pattern.compile(regex).matcher(this).replaceAll(replacement);
}

拆分实施应该是:

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

性能损失与替换方法中的性能损失相差无几.出于某种原因,Oracle 在某些方法上提供了快速路径方法而不是其他方法.

Answer 1

你确定你提出的方法确实比String类使用的基于正则表达式的方法更快- 不仅仅是你自己的测试输入,而是程序可能输入的每一个可能的输入？它依赖于String.indexOf子串匹配,这本身就是一个天真的实现,它会受到糟糕的最坏情况性能的影响.Pattern实现更复杂的匹配算法(如KMP)完全有可能避免冗余比较.

在一般情况下,Java团队负责核心库的性能非常重视,并保持大量的使用范围很广的实际数据的内部基准.我从未遇到过正则表达式处理成为瓶颈的情况.我的常设建议是首先编写可以正常工作的最简单的代码,甚至不要开始考虑重写Java内置函数,直到分析证明它是一个瓶颈,并且你已经用尽所有其他优化途径.

关于您的最新编辑 - 首先,我不会将该split方法描述为经过大量优化.它处理了一个特殊情况,它恰好是非常常见的,并且保证不会遭受上面针对天真字符串匹配算法描述的差的最坏情况复杂性 - 分裂单个字符的文字标记.

很可能是同一特殊情况可以优化replace,并将提供一些可衡量的改进.但是看看实现这种简单优化所花费的时间 - 大约50行代码.这些代码行是有代价的,特别是当它们是Java库中最广泛使用的类的一部分时.成本有多种形式:

• 资源 - 这是50行代码,一些开发人员必须花费时间在Java语言的生命周期内编写,测试,记录和维护.
• 风险 - 这是微软漏洞超过初始测试的50个机会.
• 复杂性 - 这是50个额外的代码行,任何想要了解该方法如何工作的开发人员现在都必须花时间阅读和理解.

你的问题现在归结为"为什么这一种方法被优化以处理特殊情况,而不是另一种？" 甚至更普遍的"为什么这个特殊功能没有实现？" 除了原始作者之外,没有人可以明确地回答这个问题,但答案几乎总是要么对该功能没有足够的需求,要么认为使该功能获得的好处不值得添加它的成本.