Java性能调优:优化正则表达式的匹配效率

file

在我们的日常业务开发中经常会涉及到使用正则表达式对数据进行处理,比如String的Split()方法,它根据方法中传入的正则表达式对字符串做分割处理。

但是我们是否真的了解正则表达式,它是如何匹配的?不同的匹配方式会带来怎样的效率差别?怎样才能做到效率最优?

本篇就对“如何优化正则表达式的匹配效率?”做深入探讨。

 

一、匹配的三种方式

看下面这个例子,我们给定了一个字符串以及三个功能相同但写法略有区别的正则表达式:

String testStr = "effg";
String regular_1 = "ef{1,3}g";
String regular_2 = "ef{1,3}?g";
String regular_3 = "ef{1,3}+g";

split方法测试每个正则表达式运行的时间:

List<String> regulars = new ArrayList<>();
regulars.add(regular_1);
regulars.add(regular_2);
regulars.add(regular_3);

for(String regular : regulars){
    long start,end;
    start = System.currentTimeMillis();
    testStr.split(regular);
    end = System.currentTimeMillis();
    System.out.println((end - start) + "(ms)");
}

控制台输出(为了体现效率差别,测试的时候我将上面的字符串复制成了足够的长度):

2(ms)
1(ms)
0(ms)

可以明显看到,虽然实现了相同的匹配功能,但效率却有所区别,原因在于这三种写法定义了正则表达式的三种匹配逻辑,我们来逐一说明:

码文不易
你的关注是浩说编程持续更新的动力
浩说编程会努力做的更好

 

1、贪婪模式(Greedy): ef{1,3}g

贪婪模式是正则表达式的默认匹配方式,在该模式下,对于涉及数量的表达式,正则表达式会尽量匹配更多的内容,我用模型图来演示一下匹配逻辑

图片

到第二步的时候其实已经满足第二个条件f{1,3},但我们说过贪婪模式会尽量匹配更多的内容,所以依然停在第二个条件继续遍历字符串

图片

注意看第四步,字符g不满足匹配条件f{1,3},这个时候会触发回溯机制:指针重新回到第三个字符f处

图片

关于回溯机制

回溯是造成正则表达式效率问题的根本原因,每次匹配失败,都需要将之前比对过的数据复位且指针调回到数据的上一位置,想要优化正则表达式的匹配效率,减少回溯是关键。

回溯之后,继续从下一个条件以及下一个字符继续匹配,直到结束

图片

2、懒惰模式(Reluctant): ef{1,3}?g

与贪婪模式相反,懒惰模式则会尽量匹配更少的内容:

图片

到第二步的时候,懒惰模式会认为已经满足条件f{1,3},所以会直接判断下一条件

图片

注意,到这步因为不满足匹配条件,所以触发回溯机制,将判断条件回调到上一个

图片

回溯之后,继续从下一个条件以及下一个字符继续匹配,直到结束

图片

3、独占模式(Possessive): ef{1,3}+g

独占模式应该算是贪婪模式的一种变种,它同样会尽量匹配更多的内容,区别在于在匹配失败的情况下不会触发回溯机制,而是继续向后判断,所以该模式效率最佳

图片

在了解了三种匹配方式的匹配逻辑之后,给出第一个优化建议

 

优化建议一:

推荐在使用正则表达式的时候,采用独占模式效率最佳,因为触发回溯的概率最小。

 

二、优化正则中的分支选择

通过上面对正则表达式匹配逻辑的了解,我们不难想到,由于回溯机制的存在,带有分支选择的正则表达式必然会降低匹配效率

String testStr = "abbdfg";
String regular = "(aab|aba|abb)dfg";

在这个例子中,“aab”并未匹配,于是回溯到字符串的第一个元素重新匹配第二个分支”aba”,以此类推,直到判断完所有分支,效率问题可想而知。

那么应该如何优化呢?这里给出特定情况下的两种优化建议:

优化建议二:

首先,如果分支中存在公共前缀可以提取公共部分

String regular = "a(ab|ba|bb)dfg";

这样首先减少了公共前缀的判断次数,其次降低了分支造成的回溯频率,相比之下效率有所提升。

优化建议三:

第二种方式是,如果分支中的元素比较简单,可以使用indexOf方法匹配

testStr.indexOf("aab");
testStr.indexOf("aba");
testStr.indexOf("abb");

虽然这两个建议能够优化匹配效率,但只是相比之下的优化,分支选择的机制就决定了势必要进行多次的回溯判断,所以分支选择建议能不用就不用。

 

三、优化正则中的捕获组

捕获组在正则表达式中通常用”()”表示,它将其中匹配到的内容保存到一个数组中,以便之后使用。

例如我们想获取前端input中的内容:

String inputStr = "<input id=\"userName\">userName</input>";

定义带有捕获组的正则表达式,并输出捕获组存入数组中的内容

String regular = "(<input.*?>)(.*?)(</input>)";
Pattern pattern = Pattern.compile(regular);
Matcher matcher = pattern.matcher(inputStr);
while(matcher.find()){
  System.out.println(matcher.group(0));
  System.out.println(matcher.group(1));
  System.out.println(matcher.group(2));
  System.out.println(matcher.group(3));
}

控制台输出:

<input id=\"userName\">userName</input>
<input id=\"userName\">
userName
</input>

看到这里大家应该理解了捕获组的用法,第三行就是我们需要的内容,但需要优化的是,第二行以及第四行的内容我们并不需要,这会影响效率以及内存损耗。

对于这种情况我们可以使用”(? : )“来代替”()”,区别在于前者不会将匹配的内容存入数组:


String regular = "(?:<input.*?>)(.*?)(?:</input>)";
Pattern pattern = Pattern.compile(regular);
Matcher matcher = pattern.matcher(inputStr);
while(matcher.find()){
  System.out.println(matcher.group(0));
  System.out.println(matcher.group(1));
}

控制台输出:

<input id=\"userName\">userName</input>
userName

优化建议四:

对于存在捕获组的正则表达式,如果信息不需要保存,则使用”(?: )“来替代”()”

 

总结

本篇针对正则表达式的三个点:匹配模式、选择分支、捕获组,分析出了三个优化建议:

1、推荐在使用正则表达式的时候,采用懒惰模式和独占模式效率最佳,因为触发回溯的概率最小。

2、分支选择建议尽量避免使用,特定条件下可以采用提取公共前缀、indexOf方法优化

3、对于存在捕获组的正则表达式,如果信息不需要保存,则使用”(?:“来替代”()”

以上就是本篇的内容,希望对读者有所帮助,浩说编程帮你学到更多。

发布者:小站,转转请注明出处:http://blog.gzcity.top/4658.html

(1)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022年7月5日 10:59
下一篇 2022年7月6日 10:58

相关推荐

  • Apache Log4J2 远程代码执行漏洞处置手册

    1、漏洞概述 Apache Log4j2是一个基于Java的日志记录工具。该日志框架被大量用于业务系统开发,用来记录日志信息。此次爆发的0day漏洞触发条件为只要外部用户输入的数据会被日志记录,即可造成远程代码执行。 漏洞细节 漏洞PoC 漏洞EXP 在野利用已公开 已公开 已公开 存在 参考链接:https://issues.apache.org/jira…

    2022年8月3日
    2.5K1980
  • java方式调用apksigner对Apk 检查是否签名异常 v1、v2、v3、v4 (JAVA)

    apksigner apksigner 是 Google 官方提供的针对 Android Apk 签名和验证的专用工具,位于 Android SDK / build-tools / SDK 版本 / apksigner 。 无论是 apk 包 还是 jar 包,其本质都是 zip 格式的压缩包,如果只针对 v1 签名的话,两者的签名过程其实差不多。 apks…

    2022年12月9日
    5.4K12150
  • 查看apk安装包的miniSdkVersion、targetSdkVersion

    方式一:命令: aapt list -a *.apk | grep SdkVersion用法例如:显示的结果为16进制,需要自己转换成 10进制。 查看apk安装包的miniSdkVersion、targetSdkVersion 方式二:命令: aapt dump badging .apk如果觉得结果集太长了,可以加grep过滤一下: aapt dump b…

    2022年12月9日
    9.2K16130
  • 【云原生】Spring Cloud微服务学习路线汇总

    Spring Cloud是什么?简单来说Spring Cloud是一系列框架的组成集合。主要利用的我们现在主流应用的Spring Boot框架开发便利性、巧妙地简化了分布式系统基础设施的开发,如服务发现注册、配置中心、消息总线、负载均衡、断路器、数据监控等,都可以利用Spring Boot的开发风格做到一键启动和部署。Spring Cloud没有重复制造轮子…

    2022年6月24日
    1.3K1680
  • MySql 计算两个日期的时间差函数

    MySql计算两个日期的时间差函数 MySql计算两个日期的时间差函数TIMESTAMPDIFF用法:语法:TIMESTAMPDIFF(interval,datetime_expr1,datetime_expr2) 说明:返回日期或日期时间表达式datetime_expr1 和datetime_expr2the 之间的整数差。其结果的单位由interval …

    2022年12月15日
    18.6K46120

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

评论列表(4条)