为什么字符类比交替更快? [英] Why is a character class faster than alternation?
问题描述
在一个例子中,使用字符类似乎比交替更快:[abc]
vs (a|b|c)
我听说有人推荐它,并通过使用 Time::HiRes
的简单测试验证了它(慢了约 10 倍).
还使用 (?:a|b|c)
以防捕获括号产生差异不会改变结果.
但我不明白为什么.我认为这是因为回溯,但我在每个位置看到它的方式有 3 个字符比较,所以我不确定回溯如何影响交替.这是实现的交替性质的结果吗?
It seems that using a character class is faster than the alternation in an example like:
[abc]
vs (a|b|c)
I have heard about it being recommended and with a simple test using Time::HiRes
I verified it (~10 times slower).
Also using (?:a|b|c)
in case the capturing parenthesis makes a difference does not change the result.
But I can not understand why. I think it is because of backtracking but the way I see it at each position there are 3 character comparison so I am not sure how backtracking hits in affecting the alternation. Is it a result of the implementation's nature of alternation?
推荐答案
这是因为交替之间的OR"构造 |
回溯:如果第一个交替是不匹配,引擎必须在轮次匹配期间指针位置移动之前返回,以继续匹配下一个轮次;而字符类可以顺序前进.在禁用优化的正则表达式引擎上查看此匹配:
This is because the "OR" construct |
backtracks between the alternation: If the first alternation is not matched, the engine has to return before the pointer location moved during the match of the alternation, to continue matching the next alternation; Whereas the character class can advance sequentially. See this match on a regex engine with optimizations disabled:
Pattern: (r|f)at
Match string: carat
Pattern: [rf]at
Match string: carat
但简而言之,pcre 引擎优化这个(单个文字字符 -> 字符类)已经是一个不错的提示,表明交替是低效的.
But to be short, the fact that pcre engine optimizes this (single literal characters -> character class) away is already a decent hint that alternations are inefficient.
这篇关于为什么字符类比交替更快?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!