Java 中最快的子字符串搜索方法是什么？

Question

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

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

据我所知，在Java中，有三种内置方法可以查找字符串中的子字符串。

1. string.contains()

2. string.indexOf()

3. 正则表达式。就像string.matches("ja"))这样的东西

我的问题是：上述每种方法的运行时间是多少？哪一种方法是最快、最有效或最流行的检查列表中是否包含给定子字符串的方法。

我知道存在一些算法可以做同样的事情，例如Boyer-Moore字符串搜索算法、Knuth-Morris-Pratt算法等。我不想使用它们，因为我只有一个小字符串列表，我认为现在使用它们有点过度杀伤力。此外，对于这样一个非内置算法，我还必须输入很多额外的代码。如果您认为我的想法不正确，请随时纠正我。

- Joey

---

为什么你认为子字符串搜索是一个性能问题？ - chrylis -cautiouslyoptimistic-

这里有一个不错的例子：https://dev59.com/cG435IYBdhLWcg3wpxyx - Venkata Krishna

自己设置一些简单的性能测试应该不会太复杂！ - FrankPl

你可能还想了解一下 trie 数据结构：http://en.wikipedia.org/wiki/Trie - yshavit

Answer 1

接受的答案不正确也不完整。

• indexOf() 使用回溯算法进行简单的字符串搜索。在小型模式/文本上速度相当快，但在大型文本上性能非常差
• contains("ja") 应与 indexOf 相当（因为它委托给它）
• matches("ja") 将无法提供正确的结果，因为它只搜索完全匹配的字符串"ja"
• Pattern p = Pattern.compile("ja"); Matcher m = p.matcher("jack"); m.find(); 是使用正则表达式查找文本的正确方式。在实践中（使用大型文本），这将是仅使用java api最有效的方法。这是因为一个恒定的模式（如"ja"）将不会由Regex引擎（很慢）处理，而是由Boyer-Moore算法（很快）处理。

- CoronA

---

如果你想要类似于indexOf/contains的语义，你应该使用Pattern.compile("ja", Pattern.LITERAL)来确保字符串不会被视为正则表达式模式进行解释。即使字符串不包含特殊字符，这样做也可以节省一些 CPU 周期，因为compile方法甚至不需要搜索它们。 - Holger

Answer 2

就你提到的三个问题而言，正则表达式会慢得多，因为它需要在目标较简单时组合一个完整的状态机。对于contains和indexOf的比较...

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

也就是说，contains 方法仅仅调用了 indexOf 方法，但是每次调用可能会多创建一个 String 对象。这只是 contains 方法的一种实现方式，但是由于 contains 方法的契约是 indexOf 方法的简化版本，因此每个实现方式可能都会这样工作。

- chrylis -cautiouslyoptimistic-

---

没有额外的字符串创建 - 要么s是一个String，并且toString()将返回this（因此不会创建对象） - 要么s不是一个String，在这种情况下，在调用indexOf之前需要将其转换为String。因此，如果您需要的是contains，只需使用contains即可。 - assylias

Answer 3

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

- Brinnis

---

公正起见，您应该编译一次Pattern并重复使用它。在循环中为相同的正则表达式调用String.matches(String)是低效的。可以这样做：Pattern p = Pattern.compile("ja"); for(String s : names) p.matcher(s).matches(); - Dev

由于只有4个，这确实没有太大的差别。在循环外创建模式的差异比切换到循环内创建要大。 - Brinnis

即使被接受，这个解决方案也是不正确的。首先，“matches()”的使用方法是错误的。其次，测试样本存在偏差（更倾向于使用“indexOf()”）。第三，基准测试是手写的（参见https://dev59.com/hHRB5IYBdhLWcg3wz6UK）。我将编写单独的解决方案来纠正这些问题。 - CoronA

这个基准测试没有任何价值。因为这是一个构建不正确的微型基准测试，它会让contains()方法表现得比实际情况更糟糕，因为它是第一个被测试的，而且JVM没有预热。 - Kayaman

我使用你们提供的内容进行了更新，并使用Kotlin为Android编写了代码。当然，它应该能够产生与Java在PC上类似的结果。链接：https://dev59.com/QWMl5IYBdhLWcg3wgnSl#57508798 - android developer

Answer 4

如果你正在搜索大量字符串，我读过Aho-Corasick算法非常快，但它是在Java中本地实现的。这是Unix系统中GREP使用的相同算法，如果有帮助的话，它非常高效。这里是一个由伯克利提供的Java实现。

另请参阅：https://dev59.com/wnI-5IYBdhLWcg3wm5vN#1765616

- Skylion

Answer 5

从您的问题示例中，我假设您想进行不区分大小写的比较。这会显著减慢进程速度。因此，如果您可以容忍一些不准确性-这可能取决于需要进行比较的语言环境以及您的长文本是否一遍又一遍地搜索，那么将长文本和搜索字符串一次转换为大写，然后进行不区分大小写的搜索可能是有意义的。

- FrankPl

Answer 6

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

但是，通常情况下aString.contains()和aString.indexOf()应该完全相同。 即使正则表达式被优化得非常好，它也不会超过前两者的性能。

不，Java也不使用极其专业的算法。

- Veronica Cornejo

Answer 7

在 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()
        }
    }
}

- android developer