質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Q&A

解決済

4回答

2110閲覧

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

yukkuri_55

総合スコア240

Java

Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

0グッド

0クリップ

投稿2019/12/10 06:08

編集2019/12/10 09:15

Javaです。

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

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

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

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

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答4

0

ベストアンサー

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

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

投稿2019/12/10 07:21

編集2019/12/10 07:25
mattn

総合スコア5030

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

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

Java

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


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

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

投稿2019/12/10 06:32

LouiS0616

総合スコア35658

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

LouiS0616

2019/12/10 06:54

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

0

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

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

投稿2019/12/10 06:32

maisumakun

総合スコア145121

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

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

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

投稿2019/12/10 06:13

y_waiwai

総合スコア87719

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

maisumakun

2019/12/10 06:33

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問