正则表达式比较

Question

我（终于）开始学习正则表达式，并且我想知道这两个模式字符串之间有什么显着的区别。我试图匹配类似 "Title=Blah" 的行，并将 "Title" 和 "Blah" 匹配到两个组中。

问题出现在像 "Title=The = operator" 这样的标题上。以下是解决问题的两个选择：

^([^=]+)=(.+)$
^(.+?)=(.+)$

这两者有什么区别，无论是在性能还是功能方面？

- zildjohn01

Answer 1

第一个要求在等号之前至少有一个非等号字符才能匹配，而第二个则不需要；它可以匹配前导的"=="。

关于性能，我不认为会有实质性的差异，但如果你真的关心，唯一能做的就是对其进行剖析。我会编写一对脚本，每个脚本运行其中一个方法数十万次，并使用Unix的"time"命令计时。

- chaos

---

是的，测量和分析总是最好的；但从学术上讲，有一个更紧密的答案。首先，根据内容的不同，懒惰量词可能会产生很大的差异。如果第二个正则表达式在中等大小的HTML页面上重复运行，则速度会明显变慢。 - Jim G.

正如 Stephen C 指出的那样，这对于大多数正则表达式引擎来说很重要，它们是 DFA，而对于组成更小子集的 NDFA 正则表达式引擎来说并不重要。 - Jim G.

Answer 2

第一个需要在=之前至少有一个非=字符才能匹配，而第二个则不需要；它将匹配以==开头的内容。

根据您的内容，第一个可能会运行得更快。这里是为什么：

懒惰的替代方法
在这种情况下，有一种比使加号变成懒惰的更好的选择。我们可以使用贪婪的加号和一个取反的字符类：<[^=]+>。之所以更好，是因为回溯。当使用懒惰的加号时，引擎必须为它试图匹配的HTML标记中的每个字符进行回溯。当使用取反的字符类时，当字符串包含有效的HTML代码时，根本不会发生回溯。回溯会减慢正则表达式引擎的速度。在文本编辑器中进行单个搜索时，您不会注意到差异。但是，如果在编写脚本时在紧密循环中重复使用这样的正则表达式，您将节省大量CPU周期...

- Jim G.

---

@Jim：如果引擎是基于NDFAs的话，则可以决定是否基于单个字符预读来扩展.+?，即无需回溯。诚然，大多数正则表达式引擎>>都<<是基于DFAs的。 - Stephen C

Stephen：你说得完全正确，你的观点很相关。为了简洁起见，在我的帖子中我省略了这个细节，因为正如你所说，大多数正则表达式引擎都是DFAs。有趣的是，链接所提到的页面也提到了这一点。 - Jim G.

Answer 3

在性能方面，理论上它将取决于您使用的正则表达式实现。虽然这里可能不是这种情况，但对于有问题的正则表达式，实现之间可能存在深刻的差异。例如，应用于由N个“a”组成的字符串的正则表达式a?a?a?aaa在典型（即基于DFA的）正则表达式引擎中具有复杂度为O(N**3)。

有关更多信息，请参见Russ Cox的《正则表达式匹配可以简单快速（但在Java、Perl、PHP、Python、Ruby等语言中很慢）》。

- Stephen C

Answer 4

一个很好的问题，但不幸的是这将取决于正则表达式引擎。您需要对其进行分析以了解运行时差异。嗯，我想如果您有引擎的源代码，那么您可以做出判断，但我假设这不是情况。

- Dinah

---

没有必要解析正则表达式引擎的源代码。那将是非常费力的。正则表达式引擎往往是几种众所周知的风格之一。您可以查看Jeffrey Friedl的书籍以获得指导。这比解析正则表达式引擎的源代码要更有成效（后者至少会很复杂）。 - Jim G.

同意。我只是想说，这个问题涉及到可能与引擎有关的细节问题。虽然有些常数值是不变的，但一些更微小的问题（这些问题会因为引擎而异）可以通过检查该引擎来解决。 - Dinah

Answer 5

同时运行对比 '==test'

- user140301