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

问题描述

我需要实现一种使用 Java 在字符串 (haystack) 列表中搜索子字符串 (needles) 的方法.

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屋！