为什么字符类比交替更快？
Jim*_*Jim 12 regex perl performance character-class regex-alternation
似乎使用一个字符类比一个例子中的交替更快,比如:
[abc]vs (a|b|c)
我听说它被推荐,并且使用Time::HiRes我验证的简单测试(慢10倍).在捕获括号产生差异的情况下
也使用(?:a|b|c)不会改变结果.
但我不明白为什么.我认为这是因为回溯,但我在每个位置看到它的方式有3个字符比较所以我不确定回溯是如何影响交替的.这是实施交替性质的结果吗？
Uni*_*ron 12
这是因为"OR"构造在交替之间| 回溯:如果第一次交替不匹配,则引擎必须在交替的匹配期间指针位置移动之前返回,以继续匹配下一次交替; 而字符类可以顺序前进.在禁用优化的正则表达式引擎上查看此匹配:
Pattern: (r|f)at
Match string: carat
Pattern: [rf]at
Match string: carat
但简而言之,pcre引擎优化这个(单个字面字符 - >字符类)的事实已经是一个不错的暗示,交替是低效的.
- 很酷的图形，非常有洞察力！那些是怎么制作的？ (2认同)
- @AhmedFasih嗨!这些图片是来自[regex101.com](http://regex101.com)的Regex调试器功能的屏幕截图.您可以通过在条形图中输入正则表达式,测试字符串区域中的测试字符串,然后在左侧边栏中选择"Regex Debugger"来使其工作.要获得类似截图的黑暗主题,请选择网络界面右上角的扳手图标,然后选择"黑暗主题". (2认同)
因为类似的字符类[abc]是不可简化的并且可以被优化,而类似的交替(?:a|b|c)也可以是(?:aa(?!xx)|[^xba]*?|t(?=.[^t])t).
作者选择不优化正则表达式编译器来检查交替的所有元素是否都是单个字符.
"检查下一个字符是否在此字符类中"与"检查字符串的其余部分是否与这些正则表达式中的任何一个匹配"之间存在很大差异.
- @Jim FYI:如果交替中的所有替代方案都是常量字符串(即不是像外观一样奇特的东西),它将被优化为*trie*.因此,交替禁用任何优化并不是真的,只是一个charclass仍然比更通用的trie更有效,并且没有人因为添加单字母trie→charclass优化而进一步使复制引擎变得复杂.要查看编译正则表达式的操作码,请执行类似`perl -Mre = debug -E'qr/a | b | c /'的操作. (4认同)
| 归档时间： |
|
| 查看次数： |
1082 次 |
| 最近记录： |