JAVA进阶篇（13）— 正则表达式的性能优化（正则表达式导致C
1、正则表达式基本使用
测试demo：
private static void test2() {
String regular = "^[\\u4e00-\\u9fa5_a-zA-Z0-9]+$";
String testStr = "a_行政村行政村选择充血出现在出effg+现在重置线程这需求行政村行政村选择充血自产自销区+";
Pattern p = Pattern.compile(regular);
Matcher m = p.matcher(testStr);
boolean res = m.find();
System.out.println(res);
}
2、正则表达式三种算法
Java 语言使用的正则表达式执行引擎是 NFA (Non-deterministic finite automaton) 非确定型有穷自动机，这种引擎的特点是：功能强大、单存在回溯机制导致执行效率慢（回溯严重时可以导致机器 CPU 使用率 100%，直接卡死机器）。
测试代码：
private static void test1() {
String testStr = "a_行政村行政村选择充血出现在出effg现在重置线程这需求行政村行政村选择充血自产自销区";
String regular_1 = "^[\\u4e00-\\u9fa5_a-zA-Z0-9]+$"; //贪婪模式
String regular_2 = "^[\\u4e00-\\u9fa5_a-zA-Z0-9]++$"; //懒惰模式
String regular_3 = "^[\\u4e00-\\u9fa5_a-zA-Z0-9]+?$"; //独占模式
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();
Pattern p = Pattern.compile(regular);
Matcher m = p.matcher(testStr);
boolean res = m.find();
end = System.currentTimeMillis();
System.out.println("结果：" + JSON.toJSONString(res) + "，执行时间：" + (end - start) + "(ms)");
}
}
执行结果：
结果：true，执行时间：3(ms)
结果：true，执行时间：1(ms)
结果：true，执行时间：0(ms)
可以明显看到，虽然实现了相同的匹配功能，但效率却有所区别，原因在于这三种写法定义了正则表达式的三种匹配逻辑，我们来逐一说明：
正则表达式：ef{1,3}g
待匹配的字符串：effg
2.1 贪婪模式（默认）
语法：ef{1,3}g
原理：贪婪模式是正则表达式的默认匹配方式，在该模式下，对于涉及数量的表达式，正则表达式会尽量匹配更多的内容。
说明：我用模型图来演示一下匹配逻辑：
image.png
到第二步的时候其实已经满足第二个条件f{1,3}，但我们说过贪婪模式会尽量匹配更多的内容，所以依然停在第二个条件继续遍历字符串
image.png
注意看第四步，字符g不满足匹配条件f{1，3}，这个时候会触发回溯机制：指针重新回到第三个字符f处
image.png
关于回溯机制：
回溯是造成正则表达式效率问题的根本原因，每次匹配失败，都需要将之前比对过的数据复位且指针调回到数据的上一位置，想要优化正则表达式的匹配效率，减少回溯是关键。
回溯之后，继续从下一个条件以及下一个字符继续匹配，直到结束。
2.2 懒惰模式
语法： ef{1,3}?g
原理：与贪婪模式相反，懒惰模式会尽量匹配更少的内容。
说明：
image.png
到第二步的时候，懒惰模式会认为已经满足条件f{1,3}，所以会直接判断下一条件。
image.png
注意，到这步因为不满足匹配条件，所以触发回溯机制，将判断条件回调到上一个。
image.png
回溯之后，继续从下一个条件以及下一个字符继续匹配，直到结束。
image.png
2.3 独占模式（推荐）
语法：ef{1,3}+g
原理：独占模式应该算是贪婪模式的一种变种，它同样会尽量匹配更多的内容，区别在于在匹配失败的情况下不会触发回溯机制，而是继续向后判断，所以该模式效率最佳。
说明：
image.png
2.4 三种模式表达式
| 贪婪模式 | 懒惰模式 | 独占模式 |
|---|---|---|
| X? | X?? | X?+ |
| X* | X*? | X*+ |
| X+ | X+? | X++ |
| X{n} | X{n}? | X{n}+ |
| X{n,} | X{n,}? | X{n,}+ |
| X{n,m} | X{n,m}? | X{n,m}+ |
3 优化建议
建议1：推荐使用独占模式来优化正则比表达式，格式^[允许字符集]+ 。
建议2：推荐将Pattern 缓存下来，避免反复编译Pattern。
static final Pattern HEAVY_REGEX = Pattern.compile("(((X)*Y)*Z)*");
建议3：优化正则中的分支选择
通过上面对正则表达式匹配逻辑的了解，我们不难想到，由于回溯机制的存在，带有分支选择的正则表达式必然会降低匹配效率
String testStr = "abbdfg";
String regular = "(aab|aba|abb)dfg";
在这个例子中，"aab"并未匹配，于是回溯到字符串的第一个元素重新匹配第二个分支"aba"，以此类推，直到判断完所有分支，效率问题可想而知。
如果分支中存在公共前缀，可以进行提取：
String regular = "a(ab|ba|bb)dfg";
这样首先减少了公共前缀的判断次数，其次降低了分支造成的回溯频率，相比之下效率有所提升。
