为什么C#编译正则表达式比等效的字符串方法更快？

Question

每次我必须对字符串进行简单的包含或替换操作时,我正在搜索的术语是固定值,我发现如果我采用我的示例输入并对其进行一些分析,则使用编译的正则表达式是几乎*总是比使用String类中的等效方法更快.

我试过比较各种方法(hs是搜索的"草堆",搜索ndl的"针",repl是替换值.regex总是用RegexOptions.Compiled选项创建):

• hs.Replace( ndl, repl ) VS regex.Replace( hs, repl )
• hs.Contains( ndl ) VS regex.IsMatch( hs )

我发现相当多的讨论集中于这两种技术都更快(1,2,3,和其他的负载),但是这些讨论似乎总是集中在:

1. 使用字符串版本进行简单操作,使用正则表达式进行复杂操作(从原始性能角度来看,这似乎不一定是个好主意),或者
2. 运行测试并比较两者(对于等效测试,正则表达式版本似乎总是表现更好).

我不明白这是怎么回事:正则表达式引擎如何比同等字符串版本更快地比较任何两个字符串的子串匹配？这似乎适用于非常小或非常大的搜索空间,或搜索条件的小或大,或者搜索项是在搜索空间的早期还是晚期发生的.

那么,为什么正则表达式会更快？

---

*事实上,我唯一能够证明字符串版本比编译正则表达式更快的情况是搜索空字符串时!从单个字符串到非常长的字符串的任何其他情况都由编译的正则表达式比等效的字符串方法更快地处理.

---

更新:添加了一个条款,以澄清我正在查看在编译时已知搜索项的情况.对于动态或一次性操作,编译正则表达式的开销倾向于使结果倾斜以支持字符串方法.

Answer 1

我不明白这是怎么回事:正则表达式引擎如何比同等字符串版本更快地比较任何两个字符串的子串匹配？

我可以想到两个原因:

1. 正则表达式使用一些智能算法,如Boyer Moore(O(M/N)),而简单的字符串操作只是将针与大海捞针中的每个位置进行比较(O(N*M)).
2. 他们并没有真正做同样的事情.例如,一个人可能会进行文化不变的匹配,而另一个人可能会进行与文化相关的匹配,这可能会产生性能差异.

Answer 2

正如基类库团队写道:

在[RegexOptions.Compiled]的情况下,我们首先要解析操作码.然后我们还做了更多工作,使用Reflection.Emit将这些操作码转换为实际的IL.可以想象,这种模式可以增加启动时间,从而加快运行时间:实际上,编译需要大约一个数量级的启动时间,但运行时性能提高30%.

但是,你是一个重要的东西:模式是固定的.请注意,并非总是如此.你不能在运行时改变它!在某些情况下,灵活性将下降超过30%的性能提升.