Eug*_*sky 4 .net java regex performance
我让以下编译的正则表达式匹配一堆字符串,包括.net(N)和Java(J).通过多次运行,正则表达式1和正则表达式2之间存在一致的差异,无论是在.net还是在Java中:
??????????????????????????????????????????????????????????????????
# 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
??????????????????????????????????????????????????????????????????
可以而且应该正则表达式编译器不能展开并以其他方式将等效构造标准化为最佳表现形式吗？
如果它们"可以而且应该",那么至少可以编写一个正则表达式优化器,它在编译之前修改正则表达式字符串.
使用的代码的关键部分:
.净
// 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;
我不知道.NET,因为我没有详细研究它的源代码.
但是,在Java中,特别是Oracle/Sun实现,我可以说它可能是由于循环结构开销.
在这个答案中,每当我在Java中引用正则表达式的实现时,我指的是Oracle/Sun实现.我还没有研究过其他实现,所以我真的不能说什么.
我只是意识到这部分与这个问题没什么关系.然而,它介绍了如何以这种方式实现贪婪量词,所以我将其留在这里.
给定一个A具有贪婪量词的原子A*(重复次数在这里并不重要),贪婪量词将尝试尽可能多地匹配A,然后尝试续集(无论后来A*),失败时,回溯一次重复时间和续集重试.
问题是回溯到哪里.重新匹配整个事物只是为了找出位置是非常低效的,所以我们需要存储重复完成匹配的位置,每次重复.你重复得越多,你需要保留所有状态以进行回溯所需的内存越多,而不是提及捕获组(如果有的话).
正如问题所做的那样展开正则表达式并没有逃避上面的内存要求.
但是,对于简单的情况,例如[^@]*您知道原子A(在这种情况下[^@])只能匹配固定长度的字符串(长度1),只需要最后一个匹配位置和匹配长度来有效地执行匹配.Java的实现包括一种study检测这些固定长度模式的方法,以编译为循环实现(Pattern.Curly和Pattern.GroupCurly).
这是第一个正则表达式^[^@]+@[^@]+@[^@]+@[^@]+@[^@]+@$在编译成Pattern类中的节点链后的样子:
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;
}
}
评论/取消注释不同的生成行进行测试,并弄乱数字.我在每次测试之前通过执行正则表达式500次来预热VM,然后计算累积时间以运行正则表达式1000次.
我没有任何具体的数字要发布,因为我发现自己的结果相当不稳定.但是,从我的测试来看,我通常发现第一个正则表达式比第二个正则表达式更快.
通过生成500个字符串,每个字符串最长可达40000个字符,我发现当输入导致它们在不到10秒的时间内运行时,2个正则表达式之间的差异更加突出(大约1到2秒).当输入导致它们运行更长时间(40+秒)时,两个正则表达式都具有或多或少相同的运行时间,最多只有几百毫秒的差异.
| 归档时间： |
|
| 查看次数： |
168 次 |
| 最近记录： |