15

我需要实现一种使用 Java 在字符串列表（干草堆）中搜索子字符串（针）的方法。

更具体地说，我的应用程序有一个用户配置文件列表。如果我输入一些字母，例如“Ja”，然后搜索，那么名称中包含“ja”的所有用户都应该显示出来。例如，结果可能是“Jack”、“Jackson”、“Jason”、“Dijafu”。

据我所知，在 Java 中，有 3 种内置方法可以查看字符串中的搜索子字符串。

  1. string.contains()

  2. string.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 回答
6

至于你问的三个，正则表达式会慢得多，因为当你有一个更简单的目标时，它需要组合一个完整的状态机。对于contains对indexOf...

2114 public boolean contains(CharSequence s) {
2115     return indexOf(s.toString()) > -1;
2116 }

（即，contains仅调用indexOf，但您可能会在每次调用时产生额外的String创建。这只是 的一种实现contains，但由于 的契约contains是 的简化indexOf，这可能是每种实现的工作方式。）

于 2013-08-20T16:22:21.993 回答
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 原生实现的。如果有帮助的话，它与 GREP 在基于 Unix 的系统中使用的算法相同，并且非常有效。这是 Berkley 提供的 Java 实现。

另请参阅：https ://stackoverflow.com/a/1765616/59087

于 2013-08-20T16:28:15.440 回答
0

这取决于特定的 JRE（甚至 JDK）make/version。它还取决于/可能取决于字符串长度、包含的概率、位置等因素。获得精确性能数据的唯一方法需要设置您的确切上下文。

aString.contains()但是，大体上aString.indexOf()应该是完全一样的。即使一个正则表达式得到了极好的优化，它也不会超过前两个的性能。

不，Java 也不使用非常专业的算法。

于 2013-08-20T16:23:44.427 回答
0

Kotlin 中的基准测试（无论如何都使用 Java，因此结果大致相同），在 Android 上，使用与上述类似的方法，表明确实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 回答