为什么 ^(?:x+y){5}$ 的性能比 ^x+yx+yx+yx+yx+y$ 慢
Why is performance of ^(?:x+y){5}$ slower than ^x+yx+yx+yx+yx+y$
我让以下编译后的正则表达式匹配.net (N) 和 Java (J) 中的一堆字符串。通过多次运行，在 .net 和 Java:[=13= 中，正则表达式 1 和正则表达式 2 之间存在一致的差异]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
# regex N secs N x J secs J x
──────────────────────────────────────────────────────────────────
1 ^[^@]+@[^@]+@[^@]+@[^@]+@[^@]+@$ 8.10 1 5.67 1
2 ^(?:[^@]+@){5}$ 11.07 1.37 6.48 1.14
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
正则表达式编译器是否可以并且不应该将等效结构展开并以其他方式规范化为性能最佳的形式？
如果他们 "could and should"，至少可以编写一个 regex 优化器，它在编译之前修改 regex 字符串。
使用代码的关键位：
.net
// init
regex = new Regex(r, RegexOptions.Compiled | RegexOptions.CultureInvariant);
// test
sw = Stopwatch.Start();
foreach (var s in strs)
if (regex.isMatch(s))
matches++;
elapsed = sw.Elapsed;
Java
// init
pat = Pattern.compile(r);
// test
before = System.currentTimeMillis();
for (String s : strs)
if (pat.matcher(s).matches())
matches++;
elapsed = System.currentTimeMillis() - before;
Why is performance of ^(?:x+y){5}$ slower than ^x+yx+yx+yx+yx+y$ ?
因为Backtracking的概念来了。
正则表达式 1：
^[^@]+@[^@]+@[^@]+@[^@]+@[^@]+@$
这里没有回溯，因为每个单独的模式都匹配字符串的特定部分。
正则表达式 2：
^(?:[^@]+@){5}$
我不了解.NET，因为我没有详细研究它的源代码。
然而，在Java，特别是Oracle/Sun实现，我可以说这可能是由于循环结构开销.
在这个回答中，每当我提到 Java 中正则表达式的实现时，我指的是 Oracle/Sun 实现。其他的实现我还没研究过，所以真的不好说什么。
贪心量词
才发现这部分和题目关系不大。但是，它介绍了如何以这种方式实现贪婪量词，所以我就把它留在这里。
给定一个带有贪婪量词 A* 的原子 A（重复次数在这里并不重要），贪婪量词将尝试匹配尽可能多的 A可能，然后尝试 sequel（无论 A* 之后出现什么），失败时，一次回溯一个重复，然后使用 sequel.
重试
问题是回溯到哪里。仅仅为了找出位置而重新匹配整个事情是非常低效的，因此我们需要为每次重复存储重复完成匹配的位置。重复的次数越多，就需要更多的内存来保留到目前为止的所有状态以进行回溯，更不用说捕获组（如果有的话）。
按照问题中的方式展开正则表达式不会逃避上述内存要求。
具有固定长度原子的简单情况
但是，对于简单的情况，例如 [^@]*，您知道原子 A（在本例中为 [^@]）只能匹配固定长度的字符串（长度为 1），只有最后一场比赛的位置和比赛的长度是有效进行比赛所必需的。 Java 的实现包括一个 study 方法来检测像这样的固定长度模式以编译成循环实现（Pattern.Curly 和 Pattern.GroupCurly）。
这是第一个正则表达式 ^[^@]+@[^@]+@[^@]+@[^@]+@[^@]+@$ 被编译成 Pattern 中的节点链后的样子 class:
Begin. \A or default ^
Curly. Greedy quantifier {1,2147483647}
CharProperty.complement. S̄:
BitClass. Match any of these 1 character(s):
@
Node. Accept match
Single. Match code point: U+0040 COMMERCIAL AT
Curly. Greedy quantifier {1,2147483647}
CharProperty.complement. S̄:
BitClass. Match any of these 1 character(s):
@
Node. Accept match
Single. Match code point: U+0040 COMMERCIAL AT
Curly. Greedy quantifier {1,2147483647}
CharProperty.complement. S̄:
BitClass. Match any of these 1 character(s):
@
Node. Accept match
Single. Match code point: U+0040 COMMERCIAL AT
Curly. Greedy quantifier {1,2147483647}
CharProperty.complement. S̄:
BitClass. Match any of these 1 character(s):
@
Node. Accept match
Single. Match code point: U+0040 COMMERCIAL AT
Curly. Greedy quantifier {1,2147483647}
CharProperty.complement. S̄:
BitClass. Match any of these 1 character(s):
@
Node. Accept match
Single. Match code point: U+0040 COMMERCIAL AT
Dollar(multiline=false). \Z or default $
java.util.regex.Pattern$LastNode
Node. Accept match
循环结构开销
在长度不固定的情况下，如问题中正则表达式^(?:[^@]+@){5}$中的原子(?:[^@]+@)，Java的实现切换到递归来处理匹配(Pattern.Loop).
Begin. \A or default ^
Prolog. Loop wrapper
Loop[1733fe5d]. Greedy quantifier {5,5}
java.util.regex.Pattern$GroupHead
Curly. Greedy quantifier {1,2147483647}
CharProperty.complement. S̄:
BitClass. Match any of these 1 character(s):
@
Node. Accept match
Single. Match code point: U+0040 COMMERCIAL AT
GroupTail. --[next]--> Loop[1733fe5d]
Dollar(multiline=false). \Z or default $
java.util.regex.Pattern$LastNode
Node. Accept match
这会在每次重复通过节点时产生额外开销 GroupTail --> Loop --> GroupHead。
您可能会问为什么即使重复次数是固定的，实现也会这样做。既然重复的次数是固定的，按理说，根本就没有回溯的余地，那我们不就只跟踪重复之前的状态和当前重复中的状态吗？
好吧，这是一个反例：^(?:a{1,5}?){5}$ 在长度为 15 且只有 a 的字符串上。回溯仍然可以发生在原子内部，所以我们需要像往常一样存储每次重复的匹配位置。
实际时间
我上面讨论的都是 Java 源代码（以及字节码）级别。虽然源代码可能会揭示实现中的某些问题，但性能最终取决于 JVM 如何生成机器码并进行优化。
这是我用来测试的源代码：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.regex.Pattern;
public class SO28161874 {
// Makes sure the same set of strings is generated between different runs
private static Random r = new Random();
public static void main(String args[]) {
final int rep = 5;
// String r1 = "^[^@]+@[^@]+@[^@]+@[^@]+@[^@]+@$";
String r1 = genUnroll(rep);
// String r2 = "^(?:[^@]+@){5}$";
String r2 = genQuantifier(rep);
List<String> strs = new ArrayList<String>();
// strs.addAll(generateRandomString(500, 40000, 0.002, false));
// strs.addAll(generateRandomString(500, 40000, 0.01, false));
// strs.addAll(generateRandomString(500, 40000, 0.01, true));
// strs.addAll(generateRandomString(500, 20000, 0, false));
// strs.addAll(generateRandomString(500, 40000, 0.002, true));
strs.addAll(generateNearMatchingString(500, 40000, rep));
/*
// Assertion for generateNearMatchingString
for (String s: strs) {
assert(s.matches(r1.replaceAll("[+]", "*")));
}
*/
System.out.println("Test string generated");
System.out.println(r1);
System.out.println(test(Pattern.compile(r1), strs));
System.out.println(r2);
System.out.println(test(Pattern.compile(r2), strs));
}
private static String genUnroll(int rep) {
StringBuilder out = new StringBuilder("^");
for (int i = 0; i < rep; i++) {
out.append("[^@]+@");
}
out.append("$");
return out.toString();
}
private static String genQuantifier(int rep) {
return "^(?:[^@]+@){" + rep + "}$";
}
/*
* count -- number of strings
* maxLength -- maximum length of the strings
* chance -- chance that @ will appear in the string, from 0 to 1
* end -- the string appended with @
*/
private static List<String> generateRandomString(int count, int maxLength, double chance, boolean end) {
List<String> out = new ArrayList<String>();
for (int i = 0; i < count; i++) {
StringBuilder sb = new StringBuilder();
int length = r.nextInt(maxLength);
for (int j = 0; j < length; j++) {
if (r.nextDouble() < chance) {
sb.append('@');
} else {
char c = (char) (r.nextInt(96) + 32);
if (c != '@') {
sb.append(c);
} else {
j--;
}
}
}
if (end) {
sb.append('@');
}
out.add(sb.toString());
}
return out;
}
/*
* count -- number of strings
* maxLength -- maximum length of the strings
* rep -- number of repetitions of @
*/
private static List<String> generateNearMatchingString(int count, int maxLength, int rep) {
List<String> out = new ArrayList<String>();
int pos[] = new int[rep - 1]; // Last @ is at the end
for (int i = 0; i < count; i++) {
StringBuilder sb = new StringBuilder();
int length = r.nextInt(maxLength);
for (int j = 0; j < pos.length; j++) {
pos[j] = r.nextInt(length);
}
Arrays.sort(pos);
int p = 0;
for (int j = 0; j < length - 1; j++) {
if (p < pos.length && pos[p] == j) {
sb.append('@');
p++;
} else {
char c = (char) (r.nextInt(95) + 0x20);
if (c != '@') {
sb.append(c);
} else {
j--;
}
}
}
sb.append('@');
out.add(sb.toString());
}
return out;
}
private static long test(Pattern re, List<String> strs) {
int matches = 0;
// 500 rounds warm-up
for (int i = 0; i < 500; i++) {
for (String s : strs)
if (re.matcher(s).matches());
}
long accumulated = 0;
long before = System.currentTimeMillis();
for (int i = 0; i < 1000; i++) {
matches = 0;
for (String s : strs)
if (re.matcher(s).matches())
matches++;
}
accumulated += System.currentTimeMillis() - before;
System.out.println("Found " + matches + " matches");
return accumulated;
}
}
Comment/uncomment 不同的生成行进行测试，并弄乱数字。我在每次测试前通过执行正则表达式 500 次来预热 VM，然后将累积时间计时为 运行 正则表达式 1000 次。
我没有 post 的任何具体数字，因为我发现我自己的结果相当不稳定。但是，根据我的测试，我通常发现第一个正则表达式比第二个正则表达式快。
通过生成 500 个字符串，每个字符串最长可达 40000 个字符，我发现当输入导致它们 运行 时，2 个正则表达式之间的差异更加突出（大约 1 到 2 秒）不到 10 秒。当输入导致它们 运行 更长（40+ 秒）时，两个正则表达式的 运行 时间大致相同，最多相差几百毫秒。
MSDN 在他们 Backtracking in Regular Expressions
的页面上
In general, a Nondeterministic Finite Automaton (NFA) engine like the
.NET Framework regular expression engine places the responsibility for
crafting efficient, fast regular expressions on the
developer.
这听起来更像是一个蹩脚的借口，而不是对为什么不执行优化的技术上合理的解释——如果它是为了包括问题中的情况，"in general" 似乎暗示了这一点。
我让以下编译后的正则表达式匹配.net (N) 和 Java (J) 中的一堆字符串。通过多次运行，在 .net 和 Java:[=13= 中，正则表达式 1 和正则表达式 2 之间存在一致的差异]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
# regex N secs N x J secs J x
──────────────────────────────────────────────────────────────────
1 ^[^@]+@[^@]+@[^@]+@[^@]+@[^@]+@$ 8.10 1 5.67 1
2 ^(?:[^@]+@){5}$ 11.07 1.37 6.48 1.14
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
正则表达式编译器是否可以并且不应该将等效结构展开并以其他方式规范化为性能最佳的形式？
如果他们 "could and should"，至少可以编写一个 regex 优化器，它在编译之前修改 regex 字符串。
使用代码的关键位：
.net
// init
regex = new Regex(r, RegexOptions.Compiled | RegexOptions.CultureInvariant);
// test
sw = Stopwatch.Start();
foreach (var s in strs)
if (regex.isMatch(s))
matches++;
elapsed = sw.Elapsed;
Java
// init
pat = Pattern.compile(r);
// test
before = System.currentTimeMillis();
for (String s : strs)
if (pat.matcher(s).matches())
matches++;
elapsed = System.currentTimeMillis() - before;
Why is performance of
^(?:x+y){5}$slower than^x+yx+yx+yx+yx+y$?
因为Backtracking的概念来了。
正则表达式 1：
^[^@]+@[^@]+@[^@]+@[^@]+@[^@]+@$
这里没有回溯，因为每个单独的模式都匹配字符串的特定部分。
正则表达式 2：
^(?:[^@]+@){5}$
我不了解.NET，因为我没有详细研究它的源代码。
然而，在Java，特别是Oracle/Sun实现，我可以说这可能是由于循环结构开销.
在这个回答中，每当我提到 Java 中正则表达式的实现时，我指的是 Oracle/Sun 实现。其他的实现我还没研究过，所以真的不好说什么。
贪心量词
才发现这部分和题目关系不大。但是，它介绍了如何以这种方式实现贪婪量词，所以我就把它留在这里。
给定一个带有贪婪量词 A* 的原子 A（重复次数在这里并不重要），贪婪量词将尝试匹配尽可能多的 A可能，然后尝试 sequel（无论 A* 之后出现什么），失败时，一次回溯一个重复，然后使用 sequel.
问题是回溯到哪里。仅仅为了找出位置而重新匹配整个事情是非常低效的，因此我们需要为每次重复存储重复完成匹配的位置。重复的次数越多，就需要更多的内存来保留到目前为止的所有状态以进行回溯，更不用说捕获组（如果有的话）。
按照问题中的方式展开正则表达式不会逃避上述内存要求。
具有固定长度原子的简单情况
但是，对于简单的情况，例如 [^@]*，您知道原子 A（在本例中为 [^@]）只能匹配固定长度的字符串（长度为 1），只有最后一场比赛的位置和比赛的长度是有效进行比赛所必需的。 Java 的实现包括一个 study 方法来检测像这样的固定长度模式以编译成循环实现（Pattern.Curly 和 Pattern.GroupCurly）。
这是第一个正则表达式 ^[^@]+@[^@]+@[^@]+@[^@]+@[^@]+@$ 被编译成 Pattern 中的节点链后的样子 class:
Begin. \A or default ^
Curly. Greedy quantifier {1,2147483647}
CharProperty.complement. S̄:
BitClass. Match any of these 1 character(s):
@
Node. Accept match
Single. Match code point: U+0040 COMMERCIAL AT
Curly. Greedy quantifier {1,2147483647}
CharProperty.complement. S̄:
BitClass. Match any of these 1 character(s):
@
Node. Accept match
Single. Match code point: U+0040 COMMERCIAL AT
Curly. Greedy quantifier {1,2147483647}
CharProperty.complement. S̄:
BitClass. Match any of these 1 character(s):
@
Node. Accept match
Single. Match code point: U+0040 COMMERCIAL AT
Curly. Greedy quantifier {1,2147483647}
CharProperty.complement. S̄:
BitClass. Match any of these 1 character(s):
@
Node. Accept match
Single. Match code point: U+0040 COMMERCIAL AT
Curly. Greedy quantifier {1,2147483647}
CharProperty.complement. S̄:
BitClass. Match any of these 1 character(s):
@
Node. Accept match
Single. Match code point: U+0040 COMMERCIAL AT
Dollar(multiline=false). \Z or default $
java.util.regex.Pattern$LastNode
Node. Accept match
循环结构开销
在长度不固定的情况下，如问题中正则表达式^(?:[^@]+@){5}$中的原子(?:[^@]+@)，Java的实现切换到递归来处理匹配(Pattern.Loop).
Begin. \A or default ^
Prolog. Loop wrapper
Loop[1733fe5d]. Greedy quantifier {5,5}
java.util.regex.Pattern$GroupHead
Curly. Greedy quantifier {1,2147483647}
CharProperty.complement. S̄:
BitClass. Match any of these 1 character(s):
@
Node. Accept match
Single. Match code point: U+0040 COMMERCIAL AT
GroupTail. --[next]--> Loop[1733fe5d]
Dollar(multiline=false). \Z or default $
java.util.regex.Pattern$LastNode
Node. Accept match
这会在每次重复通过节点时产生额外开销 GroupTail --> Loop --> GroupHead。
您可能会问为什么即使重复次数是固定的，实现也会这样做。既然重复的次数是固定的，按理说，根本就没有回溯的余地，那我们不就只跟踪重复之前的状态和当前重复中的状态吗？
好吧，这是一个反例：^(?:a{1,5}?){5}$ 在长度为 15 且只有 a 的字符串上。回溯仍然可以发生在原子内部，所以我们需要像往常一样存储每次重复的匹配位置。
实际时间
我上面讨论的都是 Java 源代码（以及字节码）级别。虽然源代码可能会揭示实现中的某些问题，但性能最终取决于 JVM 如何生成机器码并进行优化。
这是我用来测试的源代码：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.regex.Pattern;
public class SO28161874 {
// Makes sure the same set of strings is generated between different runs
private static Random r = new Random();
public static void main(String args[]) {
final int rep = 5;
// String r1 = "^[^@]+@[^@]+@[^@]+@[^@]+@[^@]+@$";
String r1 = genUnroll(rep);
// String r2 = "^(?:[^@]+@){5}$";
String r2 = genQuantifier(rep);
List<String> strs = new ArrayList<String>();
// strs.addAll(generateRandomString(500, 40000, 0.002, false));
// strs.addAll(generateRandomString(500, 40000, 0.01, false));
// strs.addAll(generateRandomString(500, 40000, 0.01, true));
// strs.addAll(generateRandomString(500, 20000, 0, false));
// strs.addAll(generateRandomString(500, 40000, 0.002, true));
strs.addAll(generateNearMatchingString(500, 40000, rep));
/*
// Assertion for generateNearMatchingString
for (String s: strs) {
assert(s.matches(r1.replaceAll("[+]", "*")));
}
*/
System.out.println("Test string generated");
System.out.println(r1);
System.out.println(test(Pattern.compile(r1), strs));
System.out.println(r2);
System.out.println(test(Pattern.compile(r2), strs));
}
private static String genUnroll(int rep) {
StringBuilder out = new StringBuilder("^");
for (int i = 0; i < rep; i++) {
out.append("[^@]+@");
}
out.append("$");
return out.toString();
}
private static String genQuantifier(int rep) {
return "^(?:[^@]+@){" + rep + "}$";
}
/*
* count -- number of strings
* maxLength -- maximum length of the strings
* chance -- chance that @ will appear in the string, from 0 to 1
* end -- the string appended with @
*/
private static List<String> generateRandomString(int count, int maxLength, double chance, boolean end) {
List<String> out = new ArrayList<String>();
for (int i = 0; i < count; i++) {
StringBuilder sb = new StringBuilder();
int length = r.nextInt(maxLength);
for (int j = 0; j < length; j++) {
if (r.nextDouble() < chance) {
sb.append('@');
} else {
char c = (char) (r.nextInt(96) + 32);
if (c != '@') {
sb.append(c);
} else {
j--;
}
}
}
if (end) {
sb.append('@');
}
out.add(sb.toString());
}
return out;
}
/*
* count -- number of strings
* maxLength -- maximum length of the strings
* rep -- number of repetitions of @
*/
private static List<String> generateNearMatchingString(int count, int maxLength, int rep) {
List<String> out = new ArrayList<String>();
int pos[] = new int[rep - 1]; // Last @ is at the end
for (int i = 0; i < count; i++) {
StringBuilder sb = new StringBuilder();
int length = r.nextInt(maxLength);
for (int j = 0; j < pos.length; j++) {
pos[j] = r.nextInt(length);
}
Arrays.sort(pos);
int p = 0;
for (int j = 0; j < length - 1; j++) {
if (p < pos.length && pos[p] == j) {
sb.append('@');
p++;
} else {
char c = (char) (r.nextInt(95) + 0x20);
if (c != '@') {
sb.append(c);
} else {
j--;
}
}
}
sb.append('@');
out.add(sb.toString());
}
return out;
}
private static long test(Pattern re, List<String> strs) {
int matches = 0;
// 500 rounds warm-up
for (int i = 0; i < 500; i++) {
for (String s : strs)
if (re.matcher(s).matches());
}
long accumulated = 0;
long before = System.currentTimeMillis();
for (int i = 0; i < 1000; i++) {
matches = 0;
for (String s : strs)
if (re.matcher(s).matches())
matches++;
}
accumulated += System.currentTimeMillis() - before;
System.out.println("Found " + matches + " matches");
return accumulated;
}
}
Comment/uncomment 不同的生成行进行测试，并弄乱数字。我在每次测试前通过执行正则表达式 500 次来预热 VM，然后将累积时间计时为 运行 正则表达式 1000 次。
我没有 post 的任何具体数字，因为我发现我自己的结果相当不稳定。但是，根据我的测试，我通常发现第一个正则表达式比第二个正则表达式快。
通过生成 500 个字符串，每个字符串最长可达 40000 个字符，我发现当输入导致它们 运行 时，2 个正则表达式之间的差异更加突出（大约 1 到 2 秒）不到 10 秒。当输入导致它们 运行 更长（40+ 秒）时，两个正则表达式的 运行 时间大致相同，最多相差几百毫秒。
MSDN 在他们 Backtracking in Regular Expressions
的页面上In general, a Nondeterministic Finite Automaton (NFA) engine like the .NET Framework regular expression engine places the responsibility for crafting efficient, fast regular expressions on the developer.
这听起来更像是一个蹩脚的借口，而不是对为什么不执行优化的技术上合理的解释——如果它是为了包括问题中的情况，"in general" 似乎暗示了这一点。