15

Java を使用して、文字列 (干し草の山) のリストで部分文字列 (針) を検索する方法を実装する必要があります。

具体的には、私のアプリにはユーザー プロファイルのリストがあります。「Ja」などの文字を入力して検索すると、名前に「ja」が含まれるすべてのユーザーが表示されます。たとえば、結果は「Jack」、「Jackson」、「Jason」、「Dijafu」のようになります。

Java では、私が知っているように、文字列内の検索部分文字列を表示するための組み込みメソッドが 3 つあります。

  1. string.contains()

  2. 文字列.indexOf()

  3. 正規表現。それは string.matches("ja")) のようなものです

私の質問は: 上記の各メソッドの実行時間は? 文字列のリストに特定の部分文字列が含まれているかどうかを確認するための最速または最も効率的または最も一般的な方法はどれですか。

Boyer-Moore 文字列検索アルゴリズム、Knuth-Morris-Pratt アルゴリズムなど、同じことを行うアルゴリズムがいくつか存在することは知っています。文字列のリストが少ないので、それらを使用したくありません。現在、それらを使用するのはやり過ぎだと思います。また、このような非組み込みアルゴリズムに対しては、多くの余分なコーディングを入力する必要があります。私の考えが正しくないと思われる場合は、お気軽に訂正してください。

4

7 に答える 7

30

受け入れられた回答は正しくなく、完全ではありません。

  • indexOf()不一致のバックトラッキングを使用して単純な文字列検索を行います。これは小さなパターン/テキストでは非常に高速ですが、大きなテキストではパフォーマンスが非常に低下します
  • contains("ja")indexOf に匹敵する必要があります (委任するため)
  • matches("ja")完全一致を検索するため、正しい結果が返されません (文字列のみが完全"ja"に一致します) 。
  • Pattern p = Pattern.compile("ja"); Matcher m = p.matcher("jack"); m.find();正規表現でテキストを見つける正しい方法です。実際には(大きなテキストを使用して) Java API のみを使用するのが最も効率的な方法です。これは、一定のパターン ( など"ja") が正規表現エンジン (遅い) ではなく、Boyer-Moore-Algorithm (速い) によって処理されるためです。
于 2016-08-15T06:33:28.057 に答える
4 
String[] names = new String[]{"jack", "jackson", "jason", "dijafu"};
long start = 0;
long stop = 0;

//Contains
start = System.nanoTime();
for (int i = 0; i < names.length; i++){
    names[i].contains("ja");
}
stop = System.nanoTime();
System.out.println("Contains: " + (stop-start));

//IndexOf
start = System.nanoTime();
for (int i = 0; i < names.length; i++){
    names[i].indexOf("ja");
}
stop = System.nanoTime();
System.out.println("IndexOf: " + (stop-start));

//Matches
start = System.nanoTime();
for (int i = 0; i < names.length; i++){
    names[i].matches("ja");
}
stop = System.nanoTime();
System.out.println("Matches: " + (stop-start));

出力：

Contains: 16677
IndexOf: 4491
Matches: 864018
于 2013-08-20T16:26:40.480 に答える
1

あなたの質問の例から、大文字と小文字を区別しない比較を行いたいと思います。それらはプロセスをかなり遅くします。したがって、比較を行う必要があるロケールに依存する可能性があるいくつかの不正確さを受け入れることができ、長いテキストが何度も何度も検索される場合は、長いテキストを一度大文字に変換するのが理にかなっています。大文字と小文字を区別せずに検索します。

于 2013-08-20T16:28:13.993 に答える
1

大量の文字列を検索している場合、Aho-Corasickアルゴリズムは非常に高速ですが、Java でネイティブに実装されていると読んだことがあります。これは、Unix ベースのシステムで GREP が使用するのと同じアルゴリズムであり、それが役に立ち、非常に効率的です。これはBerkley提供の Java 実装です。

参照: https://stackoverflow.com/a/1765616/59087

于 2013-08-20T16:28:15.440 に答える
0

これは、特定の JRE (さらには JDK) のメーカー/バージョンに依存します。また、文字列の長さ、含まれる確率、位置などの要因にも依存します。正確なパフォーマンス データを取得する唯一の方法は、正確なコンテキストを設定することです。

ただし、一般的にはaString.contains()とaString.indexOf()はまったく同じである必要があります。また、正規表現が見事に最適化されたとしても、最初の 2 つのパフォーマンスを超えることはありません。

いいえ、Java も非常に特殊なアルゴリズムを使用していません。

于 2013-08-20T16:23:44.427 に答える
0

上記と同様のアプローチを使用する Android での Kotlin (いずれにせよ Java を使用するため、結果はほぼ同じです) のベンチマークは、実際にcontainsは に似てindexOfいますが、それを使用しているにもかかわらず、何らかの理由でより高速であることを示しています。

正規表現に関しては、実際のオブジェクトを作成し、さらに先に進むことができるため、遅くなります。

サンプル結果 (ミリ秒単位の時間):

Contains: 0
IndexOf: 5
Matches: 45

コード：

class MainActivity : AppCompatActivity() {
    override fun onCreate(savedInstanceState: Bundle?) {
        super.onCreate(savedInstanceState)
        setContentView(R.layout.activity_main)

        AsyncTask.execute {
            val itemsCount = 1000
            val minStringLength = 1000
            val maxStringLength = 1000
            val list = ArrayList<String>(itemsCount)
            val r = Random()
            val stringToSearchFor = prepareFakeString(r, 5, 10, ALPHABET_LOWERCASE + ALPHABET_UPPERCASE + DIGITS)
            for (i in 0 until itemsCount)
                list.add(prepareFakeString(r, minStringLength, maxStringLength, ALPHABET_LOWERCASE + ALPHABET_UPPERCASE + DIGITS))
            val resultsContains = ArrayList<Boolean>(itemsCount)
            val resultsIndexOf = ArrayList<Boolean>(itemsCount)
            val resultsRegEx = ArrayList<Boolean>(itemsCount)
            //Contains
            var start: Long = System.currentTimeMillis()
            var stop: Long = System.currentTimeMillis()
            for (str in list) {
                resultsContains.add(str.contains(stringToSearchFor))
            }
            Log.d("AppLog", "Contains: " + (stop - start))
            //IndexOf
            start = System.currentTimeMillis()
            for (str in list) {
                resultsIndexOf.add(str.indexOf(stringToSearchFor) >= 0)
            }
            stop = System.currentTimeMillis()
            Log.d("AppLog", "IndexOf: " + (stop - start))
            //Matches
            val regex = stringToSearchFor.toRegex()
            start = System.currentTimeMillis()
            for (str in list) {
                resultsRegEx.add(regex.find(str) != null)
            }
            stop = System.currentTimeMillis()
            Log.d("AppLog", "Matches: " + (stop - start))
            Log.d("AppLog", "checking results...")
            var foundIssue = false
            for (i in 0 until itemsCount) {
                if (resultsContains[i] != resultsIndexOf[i] || resultsContains[i] != resultsRegEx[i]) {
                    foundIssue = true
                    break
                }
            }
            Log.d("AppLog", "done. All results are the same?${!foundIssue}")
        }
    }

    companion object {
        const val ALPHABET_LOWERCASE = "qwertyuiopasdfghjklzxcvbnm"
        const val ALPHABET_UPPERCASE = "QWERTYUIOPASDFGHJKLZXCVBNM"
        const val DIGITS = "1234567890"

        fun prepareFakeString(r: Random, minLength: Int, maxLength: Int, charactersToChooseFrom: String): String {
            val length = if (maxLength == minLength) maxLength else r.nextInt(maxLength - minLength) + minLength
            val sb = StringBuilder(length)
            for (i in 0 until length)
                sb.append(charactersToChooseFrom[r.nextInt(charactersToChooseFrom.length)])
            return sb.toString()
        }
    }
}
于 2019-08-15T11:12:14.883 に答える