哪个是更高效的正则表达式？

Question

我最近收到了一些求职者测试结果,其中一个人声称他们给出的解决方案更有效率(我不会说哪个,因为我不想影响答案).毋庸置疑,我对此表示怀疑,但我对RE编译器的内部工作原理并不了解,以便进行智能评论.

问题是:给出正则表达式来识别0到99之间的数字.

答案是:

[0-9]{1,2}
[0-9]?[0-9]
[0-9]|([0-9][0-9])

我感兴趣的是为什么其中任何一个更快(或以其他任何方式更好).提供证据而不是猜想的奖励点,但如果你说得足够令人信服,我仍然会猜测:-)

Answer 1

表达式[0-9]{1,2}应该是我想象的最快,尽管它取决于具体的引擎.

我的理由是:

• [0-9] {1,2} - 这完全描述了你想要匹配的内容.
• [0-9]？[0-9] - 如果第一场比赛失败,这可能会导致回溯.
• [0-9] |([0-9] [0-9]) - 如果失败则需要检查第一个字符两次,这里的括号是不必要的并导致不需要的捕获.

以下是我在.NET中测试时所获得的每秒迭代次数(没有RegexOptions.Compiled):

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

并作为图表:

注意:我修改了每个正则表达式以要求完全匹配而不是执行搜索.

Answer 2

至少在理论上,像这样的相同正则数将产生相同的自动机.基于DFA的匹配器将一次匹配一个字符并且在其状态中编码不同的可能分支(而不是一次取一个分支然后在失败时回溯),因此每个分支的性能将是相同的.

所有三个正则表达式都将与此DFA匹配:

+---+  0-9  +---+  0-9  +---+  *  .---.
| A |  -->  | B |  -->  | C | --> (ERR)
+---+       +---+       +---+     '---'
  |          / \          |
  | *     * /   \ $       | $ 
  V        /     \        V
.---.     /       \     .---.
(ERR) <--'         '--> (ACC)
'---'                   '---'

状态A:开始状态.如果它看到一个数字,则转到B,否则转到ERROR状态.
状态B:到目前为止匹配一位数.EOL($)已被接受.数字移动到C.其他任何内容都是错误.
状态C:两位数匹配.EOL已被接受,其他任何内容都是错误的.

这是我的语言理论答案.我不能说现实世界的正则表达式引擎实现.我忽略了括号的捕获语义,因为我猜这不是问题的关键.Automata也不处理其他"非理论"结构,如贪婪,前瞻等.至少不在他们的教科书演示中.