最近我收到了一些职位申请者的测试结果，其中一个人声称他提出的解决方案更有效（我不会说是谁，因为我不想影响答案）。毋庸置疑，我对此持怀疑态度，但是我对 RE 编译器的内部工作原理了解不够，因此无法进行有意义的评论。
问题是：给出一个正则表达式来识别从 0 到 99 的数字。
答案如下：
[0-9]{1,2}
[0-9]?[0-9]
[0-9]|([0-9][0-9])
我很想知道为什么这些方案更快（或在其他方面更好）。如果能提供证据，那就更好了，但是如果你的猜测听起来足够有说服力，我也会接受的 :-)
[0-9]{1,2}应该是最快的，尽管这取决于具体的引擎。Regex 100% valid input 50% valid input 100% invalid input
"^[0-9]{1,2}$" 749086 800313 870748
"^[0-9]?[0-9]$" 731951 725984 740152
"^(?:[0-9]|([0-9][0-9]))$" 564654 687248 870378
使用RegexOptions.Compiled：
Regex 100% valid input 50% valid input 100% invalid input
"^[0-9]{1,2}$" 1486212 1592535 1831843
"^[0-9]?[0-9]$" 1301557 1448812 1559193
"^(?:[0-9]|([0-9][0-9]))$" 1131179 1303213 1394146
作为图表：
| 实际上不应该导致回溯；这是模式匹配中的常见情况。 - Lucero^(?:[0-9]|(?:[0-9][0-9]))$。我的直觉告诉我，捕获是导致在输入无效字符串时加速的原因。 - John Kugelman理论上，像这样相同的正则表达式将产生相同的自动机。基于DFA的匹配器将一次匹配一个字符，并在其状态中编码不同的可能分支（而不是一次走一条分支，然后在失败时回溯），因此每个匹配器的性能都将相同。
这个DFA将匹配所有三个正则表达式：
+---+ 0-9 +---+ 0-9 +---+ * .---.
| A | --> | B | --> | C | --> (ERR)
+---+ +---+ +---+ '---'
| / \ |
| * * / \ $ | $
V / \ V
.---. / \ .---.
(ERR) <--' '--> (ACC)
'---' '---'
这是我的语言理论答案。我不能谈论实际的正则表达式引擎实现。我忽略了括号的捕获语义，因为我猜这不是问题的重点。自动机也不处理其他“非理论”结构，如贪婪、前瞻等。至少在它们的教科书呈现中是这样的。
[0-9][0-9]? 与第一个是相同的。 - Lucero% perl -Mre=debug -ce '@pats = ( qr/[0-9]{1,2}/, qr/[0-9]?[0-9]/, qr/[0-9][0-9]|[0-9]/ )'
Compiling REx "[0-9]{1,2}"
Final program:
1: CURLY {1,2} (14)
3: ANYOF[0-9][] (0)
14: END (0)
stclass ANYOF[0-9][] minlen 1
Compiling REx "[0-9]?[0-9]"
synthetic stclass "ANYOF[0-9][]".
Final program:
1: CURLY {0,1} (14)
3: ANYOF[0-9][] (0)
14: ANYOF[0-9][] (25)
25: END (0)
stclass ANYOF[0-9][] minlen 1
Compiling REx "[0-9][0-9]|[0-9]"
Final program:
1: BRANCH (24)
2: ANYOF[0-9][] (13)
13: ANYOF[0-9][] (36)
24: BRANCH (FAIL)
25: ANYOF[0-9][] (36)
36: END (0)
minlen 1
-e syntax OK
Freeing REx: "[0-9]{1,2}"
Freeing REx: "[0-9]?[0-9]"
Freeing REx: "[0-9][0-9]|[0-9]"
查看已编译的模式确实是一个好主意。观察已编译的模式执行可能会更有教育意义。在这里，我们将同时观察两者：
% perl -Mre=debug -e '"aabbbababbaaqcccaaaabcacabba" =~ /abc|bca|cab|caab|baac|bab|aaa|bbb/'
Compiling REx "abc|bca|cab|caab|baac|bab|aaa|bbb"
Final program:
1: TRIEC-EXACT[abc] (25)
<abc>
<bca>
<cab>
<caab>
<baac>
<bab>
<aaa>
<bbb>
25: END (0)
stclass AHOCORASICKC-EXACT[abc] minlen 3
Matching REx "abc|bca|cab|caab|baac|bab|aaa|bbb" against "aabbbababbaaqcccaaaabcacabba"
Matching stclass AHOCORASICKC-EXACT[abc] against "aabbbababbaaqcccaaaabcacabba" (28 chars)
0 <> <aabbbababb> | Charid: 1 CP: 61 State: 1, word=0 - legal
1 <a> <abbbababba> | Charid: 1 CP: 61 State: 2, word=0 - legal
2 <aa> <bbbababbaa> | Charid: 2 CP: 62 State: 11, word=0 - fail
2 <aa> <bbbababbaa> | Fail transition to State: 2, word=0 - legal
3 <aab> <bbababbaaq> | Charid: 2 CP: 62 State: 3, word=0 - fail
3 <aab> <bbababbaaq> | Fail transition to State: 5, word=0 - legal
4 <aabb> <bababbaaqc> | Charid: 2 CP: 62 State: 13, word=0 - legal
5 <aabbb> <ababbaaqcc> | Charid: 1 CP: 61 State: 14, word=8 - accepting
Matches word #8 at position 2. Trying full pattern...
2 <aa> <bbbababbaa> | 1:TRIEC-EXACT[abc](25)
2 <aa> <bbbababbaa> | State: 1 Accepted: 0 Charid: 2 CP: 62 After State: 5
3 <aab> <bbababbaaq> | State: 5 Accepted: 0 Charid: 2 CP: 62 After State: 13
4 <aabb> <bababbaaqc> | State: 13 Accepted: 0 Charid: 2 CP: 62 After State: 14
5 <aabbb> <ababbaaqcc> | State: 14 Accepted: 1 Charid: 8 CP: 0 After State: 0
got 1 possible matches
only one match left: #8 <bbb>
5 <aabbb> <ababbaaqcc> | 25:END(0)
Match successful!
Freeing REx: "abc|bca|cab|caab|baac|bab|aaa|bbb"
编译器对此进行了巧妙的处理，将其编译为Aho-Corasick trie结构。显然，这与在同一程序上运行正常回溯NFA的方式有很大不同。
无论如何，以下是您模式的时间安排，或接近它们的时间安排。我为第二个添加了另一种表述，并交换了第三个备选方案的顺序。
testing against short_fail
Rate second first third second_alt
second 9488823/s -- -9% -21% -29%
first 10475308/s 10% -- -13% -22%
third 11998438/s 26% 15% -- -11%
second_alt 13434377/s 42% 28% 12% --
testing against long_fail
Rate second first third second_alt
second 11221411/s -- -3% -5% -5%
first 11618967/s 4% -- -1% -1%
third 11776451/s 5% 1% -- -0%
second_alt 11786700/s 5% 1% 0% --
testing against short_pass
Rate first second_alt second third
first 11720379/s -- -4% -7% -7%
second_alt 12199048/s 4% -- -3% -4%
second 12593191/s 7% 3% -- -1%
third 12663378/s 8% 4% 1% --
testing against long_pass
Rate third second first second_alt
third 11135053/s -- -1% -5% -8%
second 11221655/s 1% -- -4% -7%
first 11716924/s 5% 4% -- -3%
second_alt 12042240/s 8% 7% 3% --
这是由该程序生成的：
#!/usr/bin/env perl
use Benchmark qw<cmpthese>;
$short_fail = "a" x 1;
$long_fail = "a" x 600;
$short_pass = $short_fail . 42;
$long_pass = $long_fail . 42;
for my $name (qw< short_fail long_fail short_pass long_pass >) {
print "\ntesting against $name\n";
$_ = $$name;
cmpthese 0 => {
first => '/[0-9]{1,2}/',
second => '/[0-9]?[0-9]/',
second_alt => '/[0-9][0-9]?/',
third => '/[0-9][0-9]|[0-9]/',
}
}
这里是添加了锚点的数字:
testing against short_fail
Rate first second second_alt third
first 11720380/s -- -3% -4% -11%
second 12058622/s 3% -- -1% -9%
second_alt 12180583/s 4% 1% -- -8%
third 13217006/s 13% 10% 9% --
testing against long_fail
Rate third first second_alt second
third 11378120/s -- -2% -4% -12%
first 11566419/s 2% -- -2% -10%
second_alt 11830740/s 4% 2% -- -8%
second 12860517/s 13% 11% 9% --
testing against short_pass
Rate second third second_alt first
second 11540465/s -- -5% -5% -7%
third 12093336/s 5% -- -0% -3%
second_alt 12118504/s 5% 0% -- -2%
first 12410348/s 8% 3% 2% --
testing against long_pass
Rate first second second_alt third
first 11423466/s -- -1% -4% -7%
second 11545540/s 1% -- -3% -7%
second_alt 11870086/s 4% 3% -- -4%
third 12348377/s 8% 7% 4% --
这是产生第二组数字的最小修改程序：
#!/usr/bin/env perl
use Benchmark qw<cmpthese>;
$short_fail = 1 . "a";
$long_fail = 1 . "a" x 600;
$short_pass = 2;
$long_pass = 42;
for my $name (qw< short_fail long_fail short_pass long_pass >) {
print "testing against $name\n";
$_ = $$name;
cmpthese 0 => {
first => '/^(?:[0-9]{1,2})$/',
second => '/^(?:[0-9]?[0-9])$/',
second_alt => '/^(?:[0-9][0-9]?)$/',
third => '/^(?:[0-9][0-9]|[0-9])$/',
}
}
[0-9]?[0-9] - 对于只有一个数字的情况，引擎会贪婪地匹配第一个数字，然后失败第二个；回溯然后成功。
[0-9]|([0-9][0-9]) - 这里使用了捕获组，这会使事情变慢。import re
import time
regs = ["^[0-9]{1,2}$", "^[0-9]?[0-9]$", "^[0-9]|([0-9][0-9])$"]
numbers = [str(n) for n in range(0, 100)]
result = None
// determine loop overhead
start = time.time()
for e in xrange(0, 10000):
for n in numbers:
result = n
loop = time.time() - start
for i in regs:
r = re.compile(i)
now = time.time()
for e in xrange(0, 10000):
for n in numbers:
result = r.search(n)
print (time.time() - now) - loop
秒速结果
0.874
0.869
0.809
JavaScript
var regs = ["^[0-9]{1,2}$", "^[0-9]?[0-9]$", "^[0-9]|([0-9][0-9])$"]
var numbers = [];
for(var n = 0; n < 100; n++) {
numbers.push(''+n);
}
// determine loop overhead
var result = null;
var start = new Date().getTime();
for(var e = 0; e < 10000; e++) {
for(var n = 0; n < 100; n++) {
result = numbers[n];
}
}
// test regex
var loop = new Date().getTime() - start;
for(var i = 0; i < regs.length; i++) {
var r = new RegExp(regs[i]);
var now = new Date().getTime();
for(var e = 0; e < 10000; e++) {
for(var n = 0; n < 100; n++) {
result = r.exec(numbers[n]);
}
}
console.log((new Date().getTime() - now) - loop); //using document.write here in Browsers
}
秒级响应
Node.js
0.197
0.193
0.226
Opera 11
0.836
0.408
0.372
Firefox 4
2.039
2.491
2.488
那么我们学到了什么？Python似乎比较慢，而V8则相当快。
但是，跑分总是很有趣的！
更新：Java版本
import java.util.regex.Pattern;
public class Test {
public static void main(String args[]) {
test();
test();
test();
test();
}
public static void test() {
String regs[] = {"^[0-9]{1,2}$", "^[0-9]?[0-9]$", "^[0-9]|([0-9][0-9])$"};
String numbers[] = new String[100];
for(int n = 0; n < 100; n++) {
numbers[n] = Integer.toString(n);
}
// determine loop overhead
String nresult = "";
long start = System.nanoTime();
for(int e = 0; e < 10000; e++) {
for(int n = 0; n < 100; n++) {
nresult = numbers[n];
}
}
long loop = System.nanoTime() - start;
boolean result = false;
for(int i = 0; i < regs.length; i++) {
Pattern p = Pattern.compile(regs[i]);
long now = System.nanoTime();
for(int e = 0; e < 10000; e++) {
for(int n = 0; n < 100; n++) {
result = p.matcher(numbers[i]).matches();
}
}
System.out.println(((System.nanoTime() - now) - loop) / 1000000);
}
System.out.println(result);
System.out.println(nresult);
}
}
秒级结果（第四次运行的时间）
0.230
0.262
0.210
numbers = [str(n) for n in range(0, 100)] - Ivo Wetzel就像 C 和 ++i 与 i=i+1 一样，一个好的正则表达式编译器应该将这三个编译成 完全相同的有限自动机。如果它没有做到，我会认为那是一个 bug。
（例外情况：如果启用了括号子表达式标记，则第三个显然会编译包含额外的标记信息。）
这些正则表达式非常简单，不应该有什么问题。然而，如果我必须选择更有效的实现，那么它将是 [0-9]{1,2} 或者 [0-9][0-9]?，这两个选项都不在你的选择范围内，因为它们不需要回溯。