极客时间已完结课程限时免费阅读

04 | 慎重使用正则表达式

04 | 慎重使用正则表达式-极客时间

04 | 慎重使用正则表达式

2019-05-28 刘超 来自北京
《Java性能调优实战》
课程介绍

讲述：李良

时长13:01大小11.90M

你好，我是刘超。
上一讲，我在讲 String 对象优化时，提到了 Split() 方法，该方法使用的正则表达式可能引起回溯问题，今天我们就来深入了解下，这究竟是怎么回事？
开始之前，我们先来看一个案例，可以帮助你更好地理解内容。
在一次小型项目开发中，我遇到过这样一个问题。为了宣传新品，我们开发了一个小程序，按照之前评估的访问量，这次活动预计参与用户量 30W+，TPS（每秒事务处理量）最高 3000 左右。
这个结果来自我对接口做的微基准性能测试。我习惯使用 ab 工具（通过 yum -y install httpd-tools 可以快速安装）在另一台机器上对 http 请求接口进行测试。
我可以通过设置 -n 请求数 /-c 并发用户数来模拟线上的峰值请求，再通过 TPS、RT（每秒响应时间）以及每秒请求时间分布情况这三个指标来衡量接口的性能，如下图所示（图中隐藏部分为我的服务器地址）：
就在做性能测试的时候，我发现有一个提交接口的 TPS 一直上不去，按理说这个业务非常简单，存在性能瓶颈的可能性并不大。
我迅速使用了排除法查找问题。首先将方法里面的业务代码全部注释，留一个空方法在这里，再看性能如何。这种方式能够很好地区分是框架性能问题，还是业务代码性能问题。
我快速定位到了是业务代码问题，就马上逐一查看代码查找原因。我将插入数据库操作代码加上之后，TPS 稍微下降了，但还是没有找到原因。最后，就只剩下 Split() 方法操作了，果然，我将 Split() 方法加入之后，TPS 明显下降了。
可是一个 Split() 方法为什么会影响到 TPS 呢？下面我们就来了解下正则表达式的相关内容，学完了答案也就出来了。

什么是正则表达式？

很基础，这里带你简单回顾一下。
正则表达式是计算机科学的一个概念，很多语言都实现了它。正则表达式使用一些特定的元字符来检索、匹配以及替换符合规则的字符串。
构造正则表达式语法的元字符，由普通字符、标准字符、限定字符（量词）、定位字符（边界字符）组成。详情可见下图：

正则表达式引擎

正则表达式是一个用正则符号写出的公式，程序对这个公式进行语法分析，建立一个语法分析树，再根据这个分析树结合正则表达式的引擎生成执行程序（这个执行程序我们把它称作状态机，也叫状态自动机），用于字符匹配。
而这里的正则表达式引擎就是一套核心算法，用于建立状态机。
目前实现正则表达式引擎的方式有两种：DFA 自动机（Deterministic Final Automaton 确定有限状态自动机）和 NFA 自动机（Non deterministic Finite Automaton 非确定有限状态自动机）。
对比来看，构造 DFA 自动机的代价远大于 NFA 自动机，但 DFA 自动机的执行效率高于 NFA 自动机。
假设一个字符串的长度是 n，如果用 DFA 自动机作为正则表达式引擎，则匹配的时间复杂度为 O(n)；如果用 NFA 自动机作为正则表达式引擎，由于 NFA 自动机在匹配过程中存在大量的分支和回溯，假设 NFA 的状态数为 s，则该匹配算法的时间复杂度为 O（ns）。
NFA 自动机的优势是支持更多功能。例如，捕获 group、环视、占有优先量词等高级功能。这些功能都是基于子表达式独立进行匹配，因此在编程语言里，使用的正则表达式库都是基于 NFA 实现的。
那么 NFA 自动机到底是怎么进行匹配的呢？我以下面的字符和表达式来举例说明。
text=“aabcab”
regex=“bc”
NFA 自动机会读取正则表达式的每一个字符，拿去和目标字符串匹配，匹配成功就换正则表达式的下一个字符，反之就继续和目标字符串的下一个字符进行匹配。分解一下过程。
首先，读取正则表达式的第一个匹配符和字符串的第一个字符进行比较，b 对 a，不匹配；继续换字符串的下一个字符，也是 a，不匹配；继续换下一个，是 b，匹配。
然后，同理，读取正则表达式的第二个匹配符和字符串的第四个字符进行比较，c 对 c，匹配；继续读取正则表达式的下一个字符，然而后面已经没有可匹配的字符了，结束。
这就是 NFA 自动机的匹配过程，虽然在实际应用中，碰到的正则表达式都要比这复杂，但匹配方法是一样的。

NFA 自动机的回溯

用 NFA 自动机实现的比较复杂的正则表达式，在匹配过程中经常会引起回溯问题。大量的回溯会长时间地占用 CPU，从而带来系统性能开销。我来举例说明。
text=“abbc”
regex=“ab{1,3}c”
这个例子，匹配目的比较简单。匹配以 a 开头，以 c 结尾，中间有 1-3 个 b 字符的字符串。NFA 自动机对其解析的过程是这样的：
首先，读取正则表达式第一个匹配符 a 和字符串第一个字符 a 进行比较，a 对 a，匹配。
然后，读取正则表达式第二个匹配符 b{1,3} 和字符串的第二个字符 b 进行比较，匹配。但因为 b{1,3} 表示 1-3 个 b 字符串，NFA 自动机又具有贪婪特性，所以此时不会继续读取正则表达式的下一个匹配符，而是依旧使用 b{1,3} 和字符串的第三个字符 b 进行比较，结果还是匹配。
接着继续使用 b{1,3} 和字符串的第四个字符 c 进行比较，发现不匹配了，此时就会发生回溯，已经读取的字符串第四个字符 c 将被吐出去，指针回到第三个字符 b 的位置。
那么发生回溯以后，匹配过程怎么继续呢？程序会读取正则表达式的下一个匹配符 c，和字符串中的第四个字符 c 进行比较，结果匹配，结束。

如何减少回溯问题？

既然回溯会给系统带来性能开销，那我们如何应对呢？如果你有仔细看上面那个案例的话，你会发现 NFA 自动机的贪婪特性就是导火索，这和正则表达式的匹配模式息息相关，一起来了解一下。
1. 贪婪模式（Greedy）
顾名思义，就是在数量匹配中，如果单独使用 +、 ? 、* 或{min,max} 等量词，正则表达式会匹配尽可能多的内容。
例如，上边那个例子：
text=“abbc”
regex=“ab{1,3}c”
就是在贪婪模式下，NFA 自动机读取了最大的匹配范围，即匹配 3 个 b 字符。匹配发生了一次失败，就引起了一次回溯。如果匹配结果是“abbbc”，就会匹配成功。
text=“abbbc”
regex=“ab{1,3}c”
2. 懒惰模式（Reluctant）
在该模式下，正则表达式会尽可能少地重复匹配字符。如果匹配成功，它会继续匹配剩余的字符串。
例如，在上面例子的字符后面加一个“？”，就可以开启懒惰模式。
text=“abc”
regex=“ab{1,3}?c”
匹配结果是“abc”，该模式下 NFA 自动机首先选择最小的匹配范围，即匹配 1 个 b 字符，因此就避免了回溯问题。
懒惰模式是无法完全避免回溯的，我们再通过一个例子来了解下懒惰模式在什么情况下会发生回溯问题。
text=“abbc”
regex=“ab{1,3}?c”
以上匹配结果依然是成功的，这又是为什么呢？我们可以通过懒惰模式的匹配过程来了解下原因。
首先，读取正则表达式第一个匹配符 a 和字符串第一个字符 a 进行比较，a 对 a，匹配。然后，读取正则表达式第二个匹配符 b{1,3} 和字符串的第二个字符 b 进行比较，匹配。
其次，由于懒惰模式下，正则表达式会尽可能少地重复匹配字符，匹配字符串中的下一个匹配字符 b 不会继续与 b{1,3}进行匹配，从而选择放弃最大匹配 b 字符，转而匹配正则表达式中的下一个字符 c。
此时你会发现匹配字符 c 与正则表达式中的字符 c 是不匹配的，这个时候会发生一次回溯，这次的回溯与贪婪模式中的回溯刚好相反，懒惰模式的回溯是回溯正则表达式中一个匹配字符，与上一个字符再进行匹配。如果匹配，则将匹配字符串的下一个字符和正则表达式的下一个字符。
3. 独占模式（Possessive）
同贪婪模式一样，独占模式一样会最大限度地匹配更多内容；不同的是，在独占模式下，匹配失败就会结束匹配，不会发生回溯问题。
还是上边的例子，在字符后面加一个“+”，就可以开启独占模式。
text=“abbc”
regex=“ab{1,3}+bc”
结果是不匹配，结束匹配，不会发生回溯问题。
同样，独占模式也不能避免回溯的发生，我们再拿最开始的这个例子来分析下：
text=“abbc”
regex=“ab{1,3}+c”
结果是匹配的，这是因为与贪婪模式一样，独占模式一样会最大限度地匹配更多内容，即匹配完所有的 b 之后，再去匹配 c，则匹配成功了。
讲到这里，你应该非常清楚了，在很多情况下使用懒惰模式和独占模式可以减少回溯的发生。
还有开头那道“一个 split() 方法为什么会影响到 TPS”的存疑，你应该也清楚了吧？
我使用了 split() 方法提取域名，并检查请求参数是否符合规定。split() 在匹配分组时遇到特殊字符产生了大量回溯，我当时是在正则表达式后加了一个需要匹配的字符和“+”，解决了这个问题。
\\?(([A-Za-z0-9-~_=%]++\\&{0,1})+)

正则表达式的优化

正则表达式带来的性能问题，给我敲了个警钟，在这里我也希望分享给你一些心得。任何一个细节问题，都有可能导致性能问题，而这背后折射出来的是我们对这项技术的了解不够透彻。所以我鼓励你学习性能调优，要掌握方法论，学会透过现象看本质。下面我就总结几种正则表达式的优化方法给你。

1. 少用贪婪模式，多用独占模式

贪婪模式会引起回溯问题，我们可以使用独占模式来避免回溯。前面详解过了，这里我就不再解释了。

2. 减少分支选择

分支选择类型“(X|Y|Z)”的正则表达式会降低性能，我们在开发的时候要尽量减少使用。如果一定要用，我们可以通过以下几种方式来优化：
首先，我们需要考虑选择的顺序，将比较常用的选择项放在前面，使它们可以较快地被匹配；
其次，我们可以尝试提取共用模式，例如，将“(abcd|abef)”替换为“ab(cd|ef)”，后者匹配速度较快，因为 NFA 自动机会尝试匹配 ab，如果没有找到，就不会再尝试任何选项；
最后，如果是简单的分支选择类型，我们可以用三次 index 代替“(X|Y|Z)”，如果测试的话，你就会发现三次 index 的效率要比“(X|Y|Z)”高出一些。

3. 减少捕获嵌套

在讲这个方法之前，我先简单介绍下什么是捕获组和非捕获组。
捕获组是指把正则表达式中，子表达式匹配的内容保存到以数字编号或显式命名的数组中，方便后面引用。一般一个 () 就是一个捕获组，捕获组可以进行嵌套。
非捕获组则是指参与匹配却不进行分组编号的捕获组，其表达式一般由（?:exp）组成。
在正则表达式中，每个捕获组都有一个编号，编号 0 代表整个匹配到的内容。我们可以看下面的例子：
public static void main( String[] args )
{
String text = "<input high=\"20\" weight=\"70\">test</input>";
String reg="(<input.*?>)(.*?)(</input>)";
Pattern p = Pattern.compile(reg);
Matcher m = p.matcher(text);
while(m.find()) {
System.out.println(m.group(0));//整个匹配到的内容
System.out.println(m.group(1));//(<input.*?>)
System.out.println(m.group(2));//(.*?)
System.out.println(m.group(3));//(</input>)
}
}
运行结果：
<input high=\"20\" weight=\"70\">test</input>
<input high=\"20\" weight=\"70\">
test
</input>
如果你并不需要获取某一个分组内的文本，那么就使用非捕获分组。例如，使用“(?:X)”代替“(X)”，我们再看下面的例子：
public static void main( String[] args )
{
String text = "<input high=\"20\" weight=\"70\">test</input>";
String reg="(?:<input.*?>)(.*?)(?:</input>)";
Pattern p = Pattern.compile(reg);
Matcher m = p.matcher(text);
while(m.find()) {
System.out.println(m.group(0));//整个匹配到的内容
System.out.println(m.group(1));//(.*?)
}
}
运行结果：
<input high=\"20\" weight=\"70\">test</input>
test
综上可知：减少不需要获取的分组，可以提高正则表达式的性能。

总结

正则表达式虽然小，却有着强大的匹配功能。我们经常用到它，比如，注册页面手机号或邮箱的校验。
但很多时候，我们又会因为它小而忽略它的使用规则，测试用例中又没有覆盖到一些特殊用例，不乏上线就中招的情况发生。
综合我以往的经验来看，如果使用正则表达式能使你的代码简洁方便，那么在做好性能排查的前提下，可以去使用；如果不能，那么正则表达式能不用就不用，以此避免造成更多的性能问题。

思考题

除了 Split() 方法使用到正则表达式，其实 Java 还有一些方法也使用了正则表达式去实现一些功能，使我们很容易掉入陷阱。现在就请你想一想 JDK 里面，还有哪些工具方法用到了正则表达式？
期待在留言区看到你的见解。也欢迎你点击“请朋友读”，把今天的内容分享给身边的朋友，邀请他一起学习。
分享给需要的人，Ta购买本课程，你将得18元
生成海报并分享

赞 17

提建议

© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
上一篇
03 | 字符串性能优化不容小觑，百M内存轻松存储几十G数据
下一篇
05 | ArrayList还是LinkedList？使用不当性能差千倍
unpreview
 写留言

精选留言(69)

  • Geek_99fab9
    2019-05-28
    我没有你们优秀，我就明白以后少用点正则😄

    编辑回复: 不一样的优秀～恭喜你学到了精华！

    共 2 条评论
    74
  • 胖
    2019-05-28
    字符串替换方法 Replace 普通字符替换 Replaceall 正则替换 一直觉得这两个方法的取名很具有迷惑性
    24
  • 陆离
    2019-05-28
    老师｛1，3｝的意思不是最少匹配一次，最多匹配三次吗，独占模式那个例子为什么会不匹配呢?

    作者回复: 你好，老师这里更正一下独占模式的例子，落了一个字符。ab{1,3}+bc

    18
  • K
    2019-06-01
    \\?(([A-Za-z0-9-~_=%]++\\&{0,1})+)。老师好，麻烦您讲解一下实际您当时是怎么优化的吗？从哪个正则改成了哪个正则，为什么能有这种优化。谢谢老师。

    作者回复: 如果是单个+的情况下，是最大匹配规则，遇到特殊字符串时，会出现回溯问题。这里增加了一个+，变成两个++，变成了独占模式，避免回溯。

    17
  • 没有小名的曲儿
    2019-05-28
    老师，那个(X|Y|Z)三次index是什么意思呢

    作者回复: 指的是String中的indexof方法

    共 2 条评论
    17
  • Liam
    2019-05-29
    文中提供的split性能消耗大的例子： \?(([A-Za-z0-9-~_=%]+)\&{0,1})$" 一个+ 表示量词，至少1个，不是独占模式吧，这里能否详细解释下优化点在哪里

    作者回复: 你好，一个+表示匹配一个或多个，表示尽量多的匹配。我们这个再加一个+，\\?(([A-Za-z0-9-~_=%]++\\&{0,1})+)。提供的这个是没有优化的例子。

    14
  • ID171
    2019-06-11
    还是上边的例子，在字符后面加一个“+”，就可以开启独占模式。 text=“abbc” regex=“ab{1,3}+bc” 结果是不匹配，结束匹配，不会发生回溯问题。 这里的每一步做了什么，在最大匹配之后又发生了什么
    展开

    作者回复: 1、匹配regex中的a和text中的a，匹配成功，继续匹配下一个字符； 2、匹配regex中的b{1,3}+，这个时候是最大匹配规则，也就是说text中会尽量多的去匹配b，直到满足3个b字符匹配成功，才会结束b{1,3}的匹配，这里可以直接匹配到text中的abb； 3、由于还没有满足最大3个的匹配需求，会继续匹配text中的c，发现不匹配，这个时候regex会跳到后面这个字符b，拿这个字符继续匹配； 4、regex中的b发现与text中的c不匹配，则进行回溯，回溯到text中的前一个字符b，发现匹配成功； 5、继续regex的下一个字符c与text中的c字符匹配，匹配成功，匹配结束。

    共 12 条评论
    11
  • ABC
    2019-05-30
    看完明白了回溯是什么意思，我总结如下: 回溯就比如，食堂吃饭，你一下拿了3个馒头。吃完两个，发现第三个不是你想吃的口味的时候，又把第三个放回去，这就造成了资源浪费。 避免的办法就是，一开始就只拿两个，觉得需要了再去继续拿，也就是懒惰模式。
    展开

    作者回复: 理解很到位，懒惰就是有拿到馒头就走，非常懒，还有馒头拿也不要了。

    9
  • WL
    2019-05-28
    请问一下老师 "NFA 的状态数"这个概念感觉有点抽象我不太理解, 状态数是什么意思, 是NFA可以匹配的字符串的格式枚举吗?

    作者回复: 你好 WL，就是不同的匹配格式，例如 ab{1,2}c，则状态数为2, 即 abc abbc。

    8
  • 13524265609
    2019-09-09
    非捕获分组不用括号括起来不就好了么？

    作者回复: 这个最直接了，效果是一样的

    4
  • 知易
    2020-08-11
    考古，文本"abbc" "ab{1,3}+c"匹配成功 "ab{1,3}+bc"匹配不成功时有疑惑，记录自己分析解惑流程。如有错误，欢迎指正，谢谢。 举个例子： String rgx1 = "ab{1,3}+c"; String rgx2 = "ab{1,3}+bc"; String rgx3 = "ab{1,3}+b{0,1}+c"; String text = "abbc"; 匹配流程（rgx1和text ab{1,3}+c 与 abbc）： rgx1 text a a ab ab abb abb abbb abbc(为了找到最大匹配内容，回溯一次，rgx1吐出b{1,3}+中最后一个b) abbc abbc(吐出b{1,3}+中最后一个b后，用rgx1的c和文本的c来对比，对比成功) 匹配流程（rgx2和text ab{1,3}+bc 与 abbc）： rgx2 text a a ab ab abb abb abbb abbc(为了找到最大匹配内容，回溯一次，rgx2吐出b{1,3}+中最后一个b) abbb abbc(吐出b{1,3}+中最后一个b后，用rgx2中紧跟着的b和文本的c来对比，不能回溯，对比失败) 总结，独占模式不能完全避免回溯，在通过限定字符(如b{1,3}+)会与文本比较获取最大匹配内容时回溯一次。 增加一个rgx3 和text对比 ab{1,3}+b{0,1}+c 与 abbc: rgx3 text a a ab ab abb abb abbb abbc(为了找到最大匹配内容，回溯一次，rgx3吐出b{1,3}+中最后一个b) abbb abbc(用rgx3中紧跟着的b{0,1}+和文本的c来对比，为了找到最大匹配内容，回溯一次，rgx3吐出b{0,1}+中第一个b) abbc abbc(吐出b{0,1}+中第一个b后，用rgx3中紧跟着的c和文本的c来对比，对比成功) 这里统计，为了找寻各自最大匹配内容，b{1,3}+时回溯一次，b{0,1}+时回溯一次。
    展开
    共 2 条评论
    4
  • 郁陌陵
    2019-07-05
    老师，我理解独占模式可以减少回溯，但是不能避免回溯： String regex = "^ab{1,3}+c$"; String str = "abbc"; 这个例子里，b{1,3}+ 在匹配到 abb后，无法匹配c，是需要回溯的

    作者回复: 是的，你理解的很到位，可以减少回溯，但是无法避免。这种第一次匹配会是匹配失败。具体的过程是text的a与regex的a匹配，然后继续text的b与b匹配，也匹配，这个时候由于是懒惰模式，要尽可能少的匹配，所以下一个text的b将与c匹配，匹配失败，这个时候又会回溯一次，将text的b与regex的b进行匹配，成功了，再将text中的c与c匹配，最后匹配成功。 这种方式与贪婪模式的匹配的方式是不一样的，虽然也发生了回溯，但回溯的方式不一样，是尽可能少的去匹配而发生的回溯。

    共 4 条评论
    2
  • ROAD
    2019-06-06
    replaceall
    2
  • 一步
    2020-01-09
    对与懒惰模式，是不是也有回溯的?比如下面这个： /ab{1,3}?c/.test('abbc'); // true 当第一个 b 匹配成功后，取正则表达式的下一个字符 c 去匹配字符串，然后发现下一个字符还是b就会重新取正则表达式的上一个 b

    作者回复: 是的，b与c匹配不成功之后，又会回溯到b与b匹配，成功之后，再匹配c与c，这个也是回溯。

    1
  • 稚者
    2019-09-29
    ab{1,3}+c 这个正则好诡异，既然都是独占了，也就是必须正好匹配3个，那量词 "1," 就没用了， 那就是 ab{3}+c ，可这样， 它跟 ab{3}c 岂不又是一样？

    作者回复: ab{1,3}+c 跟 ab{3}c是一样的，但独占的使用场景有很多，例如在配合.*+可以最大极限的匹配，避免发生回溯的情况下实现匹配。

    共 2 条评论
    1
  • Vincent
    2019-09-09
    正则表达式还分贪婪模式，懒惰模式，独占模式，学习到了新技能，但是对于独占模式一旦匹配失败就返回不成功，是不是有落网之鱼？

    作者回复: 是的，根据需求来定

    1
  • 钱
    2019-09-07
    课后思考及问题 任何一个细节问题，都有可能导致性能问题，而这背后折射出来的是我们对这项技术的了解不够透彻。所以我鼓励你学习性能调优，要掌握方法论，学会透过现象看本质。——严重认同，不过必须基础扎实才有机会。 没有完全懂，只知道使用正则表达式有坑，幸好我几乎不用正则表达式，以后也尽量不使用。
    展开
    1
  • Vincent
    2019-07-21
    一开始不理解什么是正则回溯问题，原来是匹配到了不要的字符。

    作者回复: 对的

    1
  • ddddd🐳
    2019-07-12
    贪婪总有存在的价值吧；贪恋相比于独占两者匹配结果是不同的，但是贪婪相比于懒惰模式呢，总有优势在吧？

    作者回复: 对的，根据业务需要来定，贪婪模式会最大匹配字符。

    1
  • Geek_d93d56
    2019-06-04
    我的测试代码 long l1 = System.currentTimeMillis(); for (int i = 0; i < 10000000; i++) { "abc".matches("ab{1,3}c"); } System.out.println("1111: " + (System.currentTimeMillis()-l1)); long l2 = System.currentTimeMillis(); for (int i = 0; i < 10000000; i++) { "abc".matches("ab{1,3}?c"); } System.out.println("2222: " + (System.currentTimeMillis()-l2)); 输出结果： 1111: 6348 2222: 6329 消耗时间差不多，没有什么差别，请问是正常的吗
    展开

    作者回复: 因为你的这个例子发生回溯非常少，几乎可以忽略了，可以写个回溯比较长的。

    1