19
20

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

String.replaceは思ったほど速くない

Last updated at Posted at 2015-04-25

一般的にJavaで何度も同じ文字列置換を行う際には、正規表現による置換が必要であればString.replaceAllではなくPattern.compileしたPatternインスタンスを使いまわし、固定文字列による置換で事足りるのであれば単にString.replaceで置換するという使い方が多いと思います。

private String regex = ...
private Patten pattern = Pattern.compile(regex);
private String masking(String input) {
    input = input.replace("yyy", "XXX");
    // input = input.replaceAll(regex, "xxx"); は遅いので書き換え
    input = pattern.matcher(input).replaceAll("xxx");
    return input;
}

これはreplaceAllの正規表現置換は結局Patternクラスを使用していて、呼び出しのたびにPattern.compileされていることが知られている一方で、固定文字列のreplaceは高速な検索・置換が可能だと考えられるからです。常識的に考えて。
しかし実際にはString.replaceはこのような実装になっています。(OpenJDK/OracleJDK:8u40)

java.lang.Stringより抜粋
public String replace(CharSequence target, CharSequence replacement) {
    return Pattern.compile(target.toString(), Pattern.LITERAL).matcher(
            this).replaceAll(Matcher.quoteReplacement(replacement.toString()));
}

驚きの手抜き実装です。なにか理由があるんでしょうか。チケットが発行されているのを見る限り、たぶんないんだと思いますが…
https://bugs.openjdk.java.net/browse/JDK-8058779

replaceの速度が欲しい場合はApache Commons LangのStringUtils.replaceを使うなどで逃げるようです。自分で適当にindexOfStringBuilderでサクッと作ってもいいかもしれません。たとえばこんな感じ。

private static String replaceByHand(final String original, final String old, final String replace) {
	int offset = 0;
	StringBuilder builder = new StringBuilder(original.length());
	int index;
	while (0 <= (index = original.indexOf(old, offset))) {
		builder.append(original, offset, index);
		builder.append(replace);
		offset = index + old.length();
	}
	builder.append(original, offset, original.length());
	return builder.toString();
}

正しい測定は面倒なので省略しますが、適当な測定によると速くなると言ってもだいたい3倍速程度です。またreplaceAllでやるように、あらかじめPattern.compile(target.toString(), Pattern.LITERAL)しておいた場合ではreplaceの1.5倍程度でした。プロファイラで出てこない限りはライブラリが何かの都合で実装していればそっちを使う程度で、積極的には置き換えるほどではない数値ですね。チケットも上がってますし将来的にJDKの方で修正されるのならそれでよさそうです。

一方で、replaceの速度がボトルネックになった場合はreplaceを置き換えるとともに文字列パターンにあった文字列探索アルゴリズムを検討するとよいかもしれません。indexOfの実装は非常にナイーブな(シンプルな)ものです。いろいろな状況に合わせる必要性を鑑みると、indexOfreplaceにおける文字列探索はおそらくナイーブなものにならざるを得ず、自動で最適化される日は将来的にも当面は来ないと思います。そのあたりPatternが上手くやってくれると期待したくなりますが、Patternのリテラル実装も同じぐらいナイーブです。

何事も疑ってかかると時間がいくらあっても足りませんが、思い込みで「上手くやってくれているはず」というのも危険という話でした。

19
20
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
19
20

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?