什么是Java中最快的子字符串搜索方法 [英] what is the fastest substring search method in Java

问题描述

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

I need to implement a way to search substring (needles) in a list of string (haystack) using Java.

更具体地说，我的应用程序有一个列表用户档案。如果我输入一些字母，例如Ja，然后搜索，则所有名称中包含ja的用户都应该显示。例如，结果可能是Jack，Jackson，Jason，Dijafu。

More specifically, my app has a list of user profiles. If I type some letters, for example, "Ja", and then search, then all the users whose name contains "ja" should show up. For instance, the result could be "Jack", "Jackson", "Jason", "Dijafu".

在Java中，据我所知，有3个构建 - 在方法中查看字符串中的搜索子字符串。

In Java, as I know, there are 3 build-in method to see search substring in a string.

1. string.contains（）

1. string.contains()

string.indexOf（）

string.indexOf()

正则表达式。它类似于string.matches（ja））

regular expression. it is something like string.matches("ja"))

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

My question is: What are the runtimes of each method above? which one is the fastest or most efficient or most popular way to check if the list of string contains a given substring.

我知道存在一些做同样事情的算法，如Boyer-Moore字符串搜索算法，Knuth-Morris-Pratt算法等。我不想使用它们，因为我只有一小串字符串，我认为使用它们对我来说有点矫枉过正。此外，我必须为这种非内置算法输入许多额外的编码。
如果您认为我的想法不正确，请随时纠正我。

I know there exists some algorithms that do the same thing, such as Boyer–Moore string search algorithm, Knuth–Morris–Pratt algorithm and so on. I do not want to use them because I just have a small list of strings, and I think using them is kind of overkill for me right now. Also I have to type a lot of extra coding for such a non-build-in algorithm. If you think my thoughts is not correct, please feel free to correct me.

推荐答案

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

这篇关于什么是Java中最快的子字符串搜索方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！