Действительно ли реализация String.replace эффективна?

Ответ 1

Чтобы дать вам представление о том, как неэффективно 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 и т.д. является попыткой быть ясными, а не эффективными. Я подозреваю, что это относится ко времени, когда многие внутренние библиотеки были написаны без соображений производительности.

IMHO 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

Захват шаблона и замена текста помогают немного, но не так сильно, как иметь обычную процедуру для замены.

Ответ 2

Есть один интересный аспект при сравнении двух решений, по крайней мере, на моей машине. Встроенная версия масштабируется намного лучше, когда дело доходит до больших строк. Учитывая слегка измененную версию вашего теста:

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

Ответ 3

String замените и замените весь метод, нет никакой разницы в эффективности или времени, и для выполнения n операции для замены charecter следующий код может помочь вам в том, как метод замены строки работает в java, вы можете проверить в своем eclipse

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