String.indexOf() と自前のindexOf() どっちが速いか？

Question

Javaです。

Java言語が用意している String.indexOf() による文字列の検索と
自前で実装したindexOf() たとえばここでは、KMP法を実装したとします。

この場合、検索する文字列にもよると思いますが、探索速度はどちらに軍配があがるのでしょうか？

ここで聞きたいのはJavaの String.indexOf() の文字列探索のアルゴリズムは
どうなっている？（何をさいようしている？）のでしょうか？

//=====回答くださった方へ（まとめて返事）=============
素人が作るプログラムより、プロの作ったプログラム、つまり String.indexOf()
の方が速い可能性が非常に高いということですね。
参考になりました。ありがとうございました。

Answer 1

アルゴリズムについてはソースが公開されているので見て下さい。勝敗については実際は様々な入力データを使ったベンチマークを取らないと答えられないです。

Java は文字列が ASCII の場合と UTF-16 の場合で処理を分けており、ASCII のみの場合は単なるバイト列として扱います。コンパクト文字列と呼ばれていますが、持ち方に合わせて検索等の実装も異なる物を使っています。UTF-16 であればバイト列を意識して検索しますし、バイト列であれば単なるバイト列検索です。この辺を本物の Java よりも良いアルゴリズムで書けるなら、勝てる可能性があるかもしれませんね。

Answer 2

OpenJDKの実装はこんな感じです。結構シンプルですね。

private static int indexOfUnsafe(byte[] value, int valueCount, byte[] str, int strCount, int fromIndex) {
...
for (int i = fromIndex; i <= max; i++) {
// Look for first character.
if (getChar(value, i) != first) {
while (++i <= max && getChar(value, i) != first);
}
// Found first character, now look at the rest of value
if (i <= max) {
int j = i + 1;
int end = j + strCount - 1;
for (int k = 1; j < end && getChar(value, j) == getChar(str, k); j++, k++);
if (j == end) {
// Found whole string.
return i;
}
}
}
return -1;
}

jdk/StringUTF16.java at master · openjdk/jdk · GitHub

---

探索速度はどちらに軍配があがるのでしょうか？

実測しないと分かりません。

Comments

[maisumakun]

呼び出し元のStringUTF16#indexOfに@HotSpotIntrinsicCandidateアノテーションがあって、プラットフォーム独自のコードの方に行ってしまうこともあるようです。

https://www.sakatakoichi.com/entry/learnintrinsics

[LouiS0616]

なるほど、そのような仕組みがあるのですね。
正直理解しきれていないのですが、主従としては『アノテーションが付いているから差し替えられる』のではなく、『差し替えられ得るメソッドにアノテーションを付け、十全に管理する』ということなのかな、と。
https://bugs.openjdk.java.net/browse/JDK-8076112

Answer 3

Javaのクラスライブラリのソースコードは、GitHubにも上がっています。

String.javaからたどってみると、UTF-16の場合の実際の処理は単純な検索でした（仮想マシンで差し替えられる可能性はあります）。

Answer 4

アルゴリズムどーこーより、そういう標準関数的なものはCとかアセンブラで書かれてるだろうから、参考にはならないと思いますよ

＃まあ、やって見る価値はあろうかと思いますが

Comments

[maisumakun]

仮想マシン側とのインターフェースが必要な部分を除けば。大半はJava自身による実装のようです。