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

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

更具体地说，我的应用程序有一个用户配置文件的列表。如果我键入一些字母，例如“Ja”，然后搜索，那么名称中包含“ja”的所有用户都应显示出来。例如，结果可能是“杰克”，“杰克逊”，“杰森”，“迪亚夫”。

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

string.contains（）
string.indexOf（）
正则表达式。它是像string.matches（ “JA”））

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

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

来源

2013-08-20 Joey

为什么你认为子字符串搜索是性能问题？ – chrylis

好一个在这里http://stackoverflow.com/questions/5296268/fastest-way-to-check-a-string-contain-another-substring-in-javascript – Krishna

它不应该是复杂的设置一些简单的性能测试你自己！ – FrankPl

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-20 16:26:40 Brinnis

公平地说，你应该编译一个'Pattern'并重用它。在同一个正则表达式的循环中调用'String.matches（String）'是效率低下的。 'Pattern p = Pattern.compile（“ja”）; for（String s：names）p.matcher（s）.matches（）;' – Dev

由于它只有4个，所以它的确有很大的不同。运行之间的差异大于在for循环之外创建模式的差异切换。 – Brinnis

该解决方案即使被接受也不正确。首先：'matches（）'以错误的方式使用。其次，测试样本有偏见（宁愿选择index）。第三：基准是手写的（请参阅http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java）。我会写一个单独的解决方案来纠正这些事实。 – CoronA

就你问到的三个问题而言，正则表达式会慢得多，因为当你有一个更简单的目标时，它需要将一个完整的状态机放在一起。对于contains VS indexOf ...

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

（即contains只是调用indexOf，但你可能在每次调用产生额外String创造，这仅仅是一个contains实施，但由于contains合同是简化indexOf，这可能是每个实现的工作原理。）

来源

2013-08-20 16:22:21 chrylis

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

但是，通常aString.contains()和aString.indexOf()应该完全一样。即使正则表达式得到了极好的优化，也不会超过前两项的表现。

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

来源

2013-08-20 16:23:44

从你的问题的例子中，我假设你想要做的不区分大小写的比较。这大大减缓了这一进程。因此，如果您可以忍受一些不准确的地方 - 这可能取决于您需要进行比较的语言环境，并且您的长文本会一遍又一遍地搜索，那么将长文本一次转换为大写可能有意义，并且搜索字符串，然后搜索不区分大小写。

来源

2013-08-20 16:28:13 FrankPl

如果您正在搜索大量字符串，我已阅读Aho-Corasick算法速度非常快，但它本身是用Java实现的。这与GREP在基于Unix的系统中使用的算法相同，只要这有助于提高效率。 Here是Berkley提供的Java实现。

参见：https://stackoverflow.com/a/1765616/59087

来源

2013-08-20 16:28:15 Skylion

接受的答案是不正确和不完整的。

indexOf()不使用回溯上的错配一个天真的字符串搜索。这是相当快的小图/文但显示在大文本表现很差
contains("ja")应该是相当的indexOf（因为它委托给它）
matches("ja")将不会带来正确的结果，因为它搜索完全匹配（只有字符串"ja"完全匹配）
Pattern p = Pattern.compile("ja"); Matcher m = p.matcher("jack"); m.find();将是使用正则表达式查找文本的正确方法。在练习（使用大文本），它将是最有效的使用java api的方式。这是因为一个恒定的模式（如"ja"）不会被正则表达式引擎处理（这是很慢的），而是通过Boyer-Moore算法（这是很快的）

来源

2016-08-15 06:33:28 CoronA

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

回答

相关问题