15

後者はパターン正規表現を使用し、前者は使用しないため、String.replace は String.replaceAll よりも高速であると考えていました。しかし実際には、パフォーマンスにも実装にも大きな違いはありません。これです：

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

ここでパターンを使用する必要は何ですか? 非正規表現置換バージョンを作成しました

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がいかに非効率的であるかを理解するために

Java7アップデート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に挿入する代わりに、コピーを1回実行することで、パフォーマンスを向上させることができます。

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

少なくとも私のマシンでは、2 つのソリューションを比較すると興味深い点が 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);
    }
}

各呼び出しで文字列の長さを 2 倍にするだけで、反復 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 の 2 つの実装を参照してください。

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 に答える