Get best of the week

我们写子串的搜索要比教科书更好



工程师的一生充满了惊奇：特别是当您必须处理生产率问题时。例如，如果您尝试运行这段Java代码，会发生什么？看起来很无辜：

//   String.repeat  JDK 11  :
final var needle = "A".repeat(500000) + "B";
final var haystack = "A".repeat(1000000) + "B";
System.out.println(haystack.indexOf(needle));

我们等待，等待，等待...至少在我的2015 OpenJDK 13笔记本电脑上，在大海捞针中找到针头大约需要一分钟。我们的老式JVM经历了数十年的性能调整，它有效地实现了内在函数String.indexOf等等。可能出了什么问题？
这是由其作者LinasMedžiūnas提供的几篇文章系列的开始，这些文章最初发表在WiX Engineering博客上。


采取什么是输入定睛一看：数据是专门挑选，以实现在最坏的情况下（二次性能O(nm)哪里n是长度haystack和m是长度needle）为天真的字符串搜索算法。我们将遍历中的所有字符haystack，如果它们与前几个字符重合，则needle我们needle将在内循环中继续运行-依此类推，直到第一个不匹配的字符为止。

您可能会认为此示例没有用，因为此类输入数据是专门设计和归档的，实际上您不会遇到这种情况。三思而后行。如果您正在处理一个Web服务，该Web服务的用户可以加载任意字符串，并且在该服务的后面某处运行代码，该怎么办？indexOf在这些线上？然后，只有少数恶意请求（如上述请求）会使您的服务瘫痪。至少值得了解有关输入数据的最坏情况。

幸运的是，存在具有线性复杂度（）的子字符串搜索算法O(n+m)。他们对上面示例中的数据没有任何问题。例如，以下Scala代码执行相同的操作，但在同一台计算机，相同的JVM上并在后台使用完全相同的代码以毫秒为单位运行java.lang.String：

val needle = "A" * 500000 + "B"
val haystack = "A" * 1000000 + "B"
println(haystack.indexOfSlice(needle))

巨大差异的秘诀在于方法内部indexOfSlice，它是Scala标准库的一部分。它实现了聪明的线性Knut-Morris-Pratt算法。不，我并不是说X语言比Y语言更好。不幸的是，这里的一切都更加复杂！例如，indexOfSlice在Scala中，这是一种通用方法，不仅适用于字符串，而且适用于其他顺序集合，并且不仅可以比较字符，还可以比较其他类型的元素。它应该比String.indexOf在中间情况下来自Java（我们将在后面讨论）。因此，我们有一个有效的算法，在最坏的情况下性能要好得多，但是平均而言，它速度较慢，因为它的常数部分要大得多。诸如此类的难题是调优性能中的典型问题。没有能够解决所有问题的神奇药丸-您需要仔细分析问题并做出正确的微基准测试。


你还在听我说吗好！您看，这只是一个介绍。我想激励您处理算法的理论复杂性和实际性能。在本文的其余部分，我们将研究几种子字符串搜索算法的一些实现及其基准。

我们将探索三种子串搜索算法。它们都在线性时间内工作，并且需要预处理，而线性依赖于长度needle。needle只需计算一次即可，然后可以在几次搜索尝试中重复使用。这是合理的，因为在许多情况下，我们需要一次又一次地搜索同一行。即使我们不这样做，预计算也不是特别昂贵的操作。

下面的所有算法都会绕过其中的每个字符haystack只能连续执行一次（不能按索引进行随机访问），因此它们在流式传输模式下都可以正常工作。本文是在基于Netty框架的生产用代理服务器上的实际工作过程中提出的，这影响了一些API设计决策。另外，由于我们需要对字节缓冲区进行搜索，因此代码将与一起使用Byte，而不是与一起使用Char。


Knut-Morris-Pratt（KMP算法）


这是一种可以追溯到上世纪70年代的著名子字符串搜索算法。它在文献中有很好的描述，因此在此不再详细描述。ILC基于状态机 -在初步计算阶段，基于构造链接索引数组needle。在搜索过程中，机器在输入处haystack一个接一个地接受字符，并相应地更新其内部状态（该状态在关系表中仅存在一个索引）。

这是Scala上的实现。

二进制子串搜索算法


最初，我不得不独立发明该算法的名称：在文献中我从未见过这样的事情。结果，我的名字叫“移位位掩码”。后来发现，该算法及其变种自1964年以来就以各种不同的英文名称而闻名，例如“ Bitap”，“ Shift-or”，“ Shift-and”，“ Baeza-Yates – Gonnet”。感谢为我找到它的读者。这篇文章早于此消息就已经写了。

该算法基于一个非常简单的想法，并且效果很好，因为几乎没有跳转，并且它基于几个原始二进制运算。因此，它限制了needle我们要查找的长度：它不能超过64个字节。这个数字只是由Long在JVM中。对于大量的实际任务，此限制足够大。

自从我自己开发此算法以来，我将尝试更详细地讨论它。首先，我们预先计算所需上下文的搜索上下文needle：

  def computeBitMasks(needle: Array[Byte]): Array[Long] = {
    require(needle.length <= 64, "Maximum supported search pattern length is 64.")
    val bitMasks = Array.ofDim[Long](256)
    var bit = 1L
    for (c <- needle) {
      bitMasks(toUnsignedInt(c)) |= bit
      bit <<= 1
    }
    bitMasks
  }

我们为每个可能的字节值（256个）预计算bitMask（64位）。对于一些字节的值，它包含了包含所有位置，其单位是。例如，下面是字符串“ abracadabra”的位掩码： 此外，您需要预先计算，这将有助于了解我们找到了完全匹配的内容。它看起来像一个值，位置有点：LongbitMaskXbitmaskXneedle



successBitMaskLong1needle.length — 1

  def computeSuccessBitMask(needle: Array[Byte]): Long = {
    1L << (needle.length - 1)
  }

最后，实际上，您需要进行搜索。我们要存储的唯一可变状态是currentMask（Long）。对于每个字节haystack，我们移位currentMask一个左1位，设置在其最显著位1，并做了逐位and的结果之间bitMask，从当前处理的字节值来计算haystack（这个and重置在那些地方所有的位currentMask不当前处理的字节匹配）。

因此，在处理完每个字节之后，只有那些处于适当位置的位才能幸免。并且在处理完每个字节后，所有位都向左移动一个位置。如果位“存活”在迭代次数等于长度needle-我们找到了火柴！我们可以使用以下方法验证这一点successBitMask：

  def process(value: Byte): Boolean = {
    currentMask = ((currentMask << 1) | 1) & bitMasks(toUnsignedInt(value))
    (currentMask & successBitMask) == 0
  }

注意：false如果发现某些内容，上述方法将返回，并且看起来违反直觉。可以理解，该值true表示需要继续搜索，但会false停止搜索-这是由于如上所述，该API已与Netty兼容。如果你想知道如何执行搜索，这里就是一个例子。

结果，所有逻辑都归结为一些简单的处理器指令。不幸的是，仍然存在对数组索引范围的完全无用的检查bitMasks，这是JDK无法删除的（我查看了由几个不同的JDK生成的汇编程序）。

这是Scala的完整实现。

Aho korasik


这是自1975年以来已知的另一种流行算法。它的独特之处（有时是非常有用的）是能够一次搜索多个needle字符，而来自其中的所有字符仅haystack被绕过一次（我认为这太棒了！）。所有这些工作的想法是对KMP算法的扩展，KMP算法是一种使用前缀树的有限状态机（基于几个树needle），其中包含指向链接的链接（与KMP中的一维数组进行比较）。基于这些链接，自动机的内部状态在每个已处理符号之后在前缀树的节点之间切换，并且某些节点指示针对特定符号的肯定搜索结果needle。这里的预计算阶段相当复杂，但是搜索阶段出乎意料地非常简单。

这是Scala上可行的实现的链接。


这是一个完全不完整的子字符串搜索算法列表。我们还尝试了Rabin-Karp算法和Boyer-Moore算法。在这两者中，Boyer-Moore表现出可比的性能，但是它们都与流媒体不兼容（使用haystack按索引的随机访问），因此我从调查中删除了它们。


基准测试


我们将对上述三种算法进行基准测试，此外，还要查看方法String.indexOf（Java）和indexOfSlice（Scala）的结果。老实说，这不是一个完全正确的比较，因为它String.indexOf适用于字符串，并且所有其他方法都位于字节数组上。但这似乎并没有使这种比较的结果无效。此外，我还包括了Bytes.indexOf番石榴（v.28.1）的结果。此方法适用于字节数组。然后他们在Google上写了-他们在那里写的所有内容都运行得非常快，对吗？

编写基准测试总是很困难，因为您可以将完全不同的数据发送到输入，并以许多不同的方式进行更改-不仅长度needle和haystack，还受这些行的内部内容的影响（这可能会大大影响某些算法）。在实践中，始终值得检查与您实际任务中的数据最相似的输入数据（这是我们在项目中所做的）。

为了简化本文，我仅使用了两种输入。其中一个旨在反映实际情况：haystack大小约为1.5 KB（内部带有人类可读文本）needle-9个字节，而不是haystack按此顺序排列（这是强制算法执行完整扫描所必需的）。

需要另一种类型的输入来获得二次算法的最坏情况。它比本文开头的数据短得多：否则，我们将不得不等待一整分钟，还记得吗？数组haystack设置为以下格式"AA...AAB"（与第一种数据类型相同的长度），以及needle-64字节（尤其是二进制子字符串搜索算法要处理的字节）相同类型的数组（匹配仅在最后haystack）。

在这里可以找到用JMH框架编写的基准。如果您对此处的测量方法和方法还有其他想法，可以克隆此存储库，更改某些内容并发表评论。

在弗拉基米尔·西特尼科夫（Vladimir Sitnikov）的建议下，我添加了基准测试结果java.util.regex.Pattern；他在后台使用了Boyer-Moore算法。


（译者注：顺便说一句，弗拉基米尔·西特尼科夫（Vladimir Sitnikov）是JUG Ru Group几个计划委员会的成员，他本人也做了有趣的报告。例如，他的JPoint 2019报告题为``Java放慢了速度：CodeCache版本'' 的视频可在链接上获得）。

基准结果


结果以毫秒为单位，越少越好： 这里的一切都与预期的一样：

# JMH version: 1.21
# VM version: JDK 13.0.1, OpenJDK 64-Bit Server VM, 13.0.1+9
Benchmark (searchInput) Mode Cnt Score Error Units
javaIndexOf REGULAR avgt 5 0.622 ± 0.002 us/op
shiftingBitMask REGULAR avgt 5 1.982 ± 0.017 us/op
regexPattern REGULAR avgt 5 2.184 ± 0.006 us/op
kmp REGULAR avgt 5 2.635 ± 0.016 us/op
scalaIndexOfSlice REGULAR avgt 5 3.202 ± 0.009 us/op
guavaIndexOf REGULAR avgt 5 3.696 ± 0.095 us/op
ahoCorasic REGULAR avgt 5 7.063 ± 0.040 us/op
shiftingBitMask WORST_CASE avgt 5 1.986 ± 0.010 us/op
kmp WORST_CASE avgt 5 5.120 ± 0.006 us/op
ahoCorasic WORST_CASE avgt 5 6.892 ± 0.025 us/op
scalaIndexOfSlice WORST_CASE avgt 5 8.765 ± 0.007 us/op
regexPattern WORST_CASE avgt 5 11.566 ± 0.086 us/op
javaIndexOf WORST_CASE avgt 5 23.029 ± 0.124 us/op
guavaIndexOf WORST_CASE avgt 5 52.927 ± 0.275 us/op



  • 对于普通数据，它占主导地位javaIndexOf，因为它在内部使用了高性能内在函数，因此常量部分很小；
  • , : , (O(nm)) javaIndexOf, — , shiftingBitMask ( ) .
  • guavaIndexOf , javaIndexOf; , 2 , shiftingBitMask;
  • scalaIndexOfSlice - , knuthMorrisPratt, , — , ;
  • 性能并不是最强大的功能ahoCorasic（或至少不是其实现的功能；我必须承认，我并没有真正尝试对其进行微优化，因为我之所以添加它仅仅是因为它的独特功能：一次可以跨几行搜索的能力，并且类似于另一篇文章的主题）；
  • 输入数据（和长度needle）不影响性能shiftingBitMask和ahoCorasic。

发现


在不同情况下，基准可以以不同方式工作。尽管上述结果似乎很有指示性，但您仍应始终自己进行测量并使用反映您实际任务的数据进行测量。

根据提供的数据，我得出以下结论：

  • String- , , String.indexOf ( java.util.regex.Pattern — );
  • , needle 64 , ;
  • , --;
  • Scala - ( ), indexOfSlice — ;
  • , -.

就这样！如果您喜欢阅读有关算法，性能等的文章（以及有关Scala，JVM和Java的一般文章），请订阅本文的作者Linas Medziunas（Medium，Twitter）。

包含本文中所有代码的github存储库在这里。


在JUG Ru Group和JPoint Conference的支持下发表文章的翻译。

More articles:


All Articles