15

我曾经认为 String.replace 比 String.replaceAll 快，因为后者使用 Pattern 正则表达式，而前者没有。但实际上无论是性能还是实现上都没有显着差异。就是这个：

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

这里有什么需要使用 Pattern 的？我写了一个非正则表达式替换版本

static String replace(String s, String target, String replacement) {
    StringBuilder sb = new StringBuilder(s);
    for (int i = 0; (i = sb.indexOf(target, i)) != -1; i += replacement.length()) {
        sb.replace(i, i + target.length(), replacement);
    }
    return sb.toString();
}

并比较性能

    public static void main(String args[]) throws Exception {
        String s1 = "11112233211";
        for (;;) {
            long t0 = System.currentTimeMillis();
            for (int i = 0; i < 1000000; i++) {
//              String s2 = s1.replace("11", "xxx");
                 String s2 = replace(s1, "11", "22");
            }
            System.out.println(System.currentTimeMillis() - t0);
        }
    }

基准测试：我的版本 - 400ms; JDK 版本 - 1700ms.

我的测试是错误的还是 String.replace 真的低效？

4

3 回答 3

12

为了让您了解 String.replace 的效率如何

来自 Java 7 更新 11 的源代码。

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

AFAIK，使用 Pattern 和 Matcher.quiteReplacement 等是为了清晰而不是高效。我怀疑它可以追溯到许多内部库在没有性能考虑的情况下编写的时候。

恕我直言，Java 7 已经看到许多内部库提高了性能，特别是减少了不必要的对象创建。这种方法是一个明显的改进候选者。

您可以通过执行一次复制来提高性能，而不是尝试插入现有的 StringBuilder。

static String replace2(String s, String target, String replacement) {
    StringBuilder sb = null;
    int start = 0;
    for (int i; (i = s.indexOf(target, start)) != -1; ) {
        if (sb == null) sb = new StringBuilder();
        sb.append(s, start, i);
        sb.append(replacement);
        start = i + target.length();
    }
    if (sb == null) return s;
    sb.append(s, start, s.length());
    return sb.toString();
}

public static void main(String... ignored) {
    String s1 = "11112233211";
    for (; ; ) {
        timeReplace(s1);
        timeReplace2(s1);
        timeStringReplaceRefactored(s1);
        timeStringReplace(s1);
    }
}

private static void timeStringReplace(String s1) {
    long start0 = System.currentTimeMillis();
    for (int i = 0; i < 1000000; i++) {
        String s2 = s1.replace("11", "xxx");
        if (s2.length() <= s1.length()) throw new AssertionError();
    }
    System.out.printf("String.replace %,d ns avg%n", System.currentTimeMillis() - start0);
}

private static void timeStringReplaceRefactored(String s1) {
    long start0 = System.currentTimeMillis();
    Pattern compile = Pattern.compile("11", Pattern.LITERAL);
    String xxx = Matcher.quoteReplacement("xxx");
    for (int i = 0; i < 1000000; i++) {
        String s2 = compile.matcher(s1).replaceAll(xxx);
        if (s2.length() <= s1.length()) throw new AssertionError();
    }
    System.out.printf("String.replace %,d ns avg (Refactored)%n", System.currentTimeMillis() - start0);
}
private static void timeReplace(String s1) {
    long start0 = System.currentTimeMillis();
    for (int i = 0; i < 1000000; i++) {
        String s2 = replace(s1, "11", "xxx");
        if (s2.length() <= s1.length()) throw new AssertionError();
    }
    System.out.printf("Replace %,d ns avg%n", System.currentTimeMillis() - start0);
}

private static void timeReplace2(String s1) {
    long start0 = System.currentTimeMillis();
    for (int i = 0; i < 1000000; i++) {
        String s2 = replace2(s1, "11", "xxx");
        if (s2.length() <= s1.length()) throw new AssertionError();
    }
    System.out.printf("My replace %,d ns avg%n", System.currentTimeMillis() - start0);
}

static String replace(String s, String target, String replacement) {
    StringBuilder sb = new StringBuilder(s);
    for (int i = 0; (i = sb.indexOf(target, i)) != -1; i += replacement.length()) {
        sb.replace(i, i + target.length(), replacement);
    }
    return sb.toString();
}

印刷

Replace 177 ns avg
My replace 108 ns avg
String.replace 436 ns avg (Refactored)
String.replace 598 ns avg

捕捉模式并替换文本会有所帮助，但不如使用自定义例程进行替换。

于 2013-01-25T08:28:24.900 回答
1

至少在我的机器上比较这两种解决方案时，有一个有趣的方面。当涉及到更大的字符串时，内置版本的扩展性要好得多。给定一个稍微修改过的测试版本：

for (int i = 0; i < 10; i++) {
    s1 = s1 + s1;
    long t0 = call1(s1); // your implementation
    long t1 = call2(s1); // 1.7_07 Oracle
    long delta = t0 - t1;

    System.out.println(
      String.format("Iteration %s, string length %s, call1 %s, call2 %s, delta %s", i, s1.length(), t0, t1, delta));

    try {
        Thread.sleep(200);
    } catch (Exception e) {
        throw new RuntimeException(e);
    }
}

通过每次调用将字符串长度加倍，在迭代 3 或 4 之后已经达到收支平衡：

Iteration 0, string length 22, call1 450, call2 1715, delta -1265
Iteration 1, string length 44, call1 1048, call2 2152, delta -1104
Iteration 2, string length 88, call1 2695, call2 4024, delta -1329
Iteration 3, string length 176, call1 7737, call2 7574, delta 163
Iteration 4, string length 352, call1 24662, call2 15560, delta 9102

作为参考 call1 和 call2 的两个实现：

static long call1(String s) {
    long t0 = System.currentTimeMillis();
    for (int i = 0; i < 1000000; i++) {
        String s2 = replace(s, "11", "22");
    }
    return System.currentTimeMillis() - t0;
}

static long call2(String s) {
    long t0 = System.currentTimeMillis();
    for (int i = 0; i < 1000000; i++) {
        String s2 = s.replace("11", "xxx");
    }
    return System.currentTimeMillis() - t0;
}
于 2013-01-25T09:07:57.507 回答
0

字符串替换和替换所有方法在效率或时间上没有差异

package com.jav.exec;

public class replace {

    static String s1="This the India the india the nation";

    public static String replace(String s2,String s3)
    {
        int counter=0;
        int count=s3.length()-1;
        int count1=0;
        char[] ca1=s1.toCharArray();
        char[] ca2=s2.toCharArray();
        char[] ca3=s3.toCharArray();

        for(int f1=0;f1<ca1.length;f1++)//finding the number of occurances
        {
            if(ca1[f1]==ca2[counter])//increasing counter if charecters matches
            {
                counter++;

                if(counter==s2.length())//if consecutive charecters makes count equal to replacing string
                {
                    count1++;//increasing the count if consecutive charecters matches the striing
                    counter=0;//making counter 0 for next occurence
                }
            }
            else
            {
                counter=0;//making counter 0 if occurence less than the string 
            }
        }

        char[] ca4=new char[ca1.length+(count1*ca3.length)-(count1*ca2.length)];
        //creating new sized array for storing values
        counter=0;
        count=s3.length()-1;
        count1=0;
        int count2=0;

        for(int f=0;f<ca4.length;f++)
        {
            ca4[f]=ca1[count2];//storing the values into the new array of original long array
            //increasing the count  
            if(ca1[count2]==ca2[counter])//if charecters matches replacing array charecters
            {
                counter++;
                if(counter==ca2.length)//if counter is equal to length of replacing array
                {
                    f=f+ca3.length-ca2.length;//increasing the count of f
                    for(int f1=0;f1<ca3.length;f1++)//storing replaced array charecters to new array
                    {
                        ca4[f-count]=ca3[count1];
                        count1++;
                        count--;
                    }
                    counter=0;//redeclaring variables to their inital values for next replacement
                    count1=0;
                    count=s3.length()-1;
                }
            }

            else
            {   
                while(counter>0)
                {   
                    ca4[f-counter]=ca1[count2-counter];
                    counter--;
                }
            }
            count2++;
        }
        return new String(ca4);
    }

    public static void main(String[] args)
    {
        System.out.println(replace("the","mother"));
    }
}
于 2017-01-18T19:13:45.977 回答