11

我不时听到人们说 Perl 中的正则表达式比其他语言更快。此外，一些在线文档还说 Perl 在正则表达式处理方面具有优势。你们能解释一下这是不是真的，为什么？

4

3 回答 3

19

当其中一个（Java 的）有明显缺陷时，为什么还要考虑两个引擎的速度呢？（搜索 Tom "tchrist" Christiansen 关于该主题的著作。）例如，\s无法匹配许多空格字符。

此外，一些在线文档还说 Perl 在正则表达式处理方面具有优势。

这里有一些：

  • 有许多你在其他引擎中找不到的特性，要么是因为其他引擎还没有复制它们，要么是因为它们的设计不允许它们支持这些特性。
  • 高度优化。其中许多优化有助于更快地报告失败的匹配，这在许多基准测试中都没有涵盖。
  • Unicode 支持的领导者。它的支持非常先进，以至于我们的开发人员发现了 Unicode 标准本身的问题并努力解决了这些问题！
  • 非常没有错误。
于 2013-06-15T00:54:06.923 回答
13

你可以看看这个基准。在表中，列patmch:1t给出了将 URL 与 匹配的时间/([a-zA-Z][a-zA-Z0-9]*)://([^ /]+)(/?[^ ]*)/，而patmch:2t将 URL 或电子邮件与匹配的列给出了/([a-zA-Z][a-zA-Z0-9]*)://([^ /]+)(/?[^ ]*)|([^ @]+)@([^ @]+)/（注意|运算符）。对于第一种模式，Perl 比 Java 快大约 10 倍；第二，它们大致相同。

通常，Perl 使用回溯正则表达式引擎。这样的引擎在正则表达式的子集上灵活、易于实现且速度非常快。但是，对于其他类型的正则表达式，例如当有|运算符时，它可能会变得非常慢。在极端情况下，它的匹配速度是模式长度的指数。另一种正则表达式引擎基于 NFA。对于所有类型的输入，它更难以实现，但性能稳定（在最坏的 IIRC 时为二次方）。Russ Cox有几篇关于这些主题的文章，我非常喜欢。

我不知道 Java 使用的是什么类型的正则表达式引擎，但从基准测试来看，它的性能似乎并不令人印象深刻。您可能还对这个在正则表达式上评估几个 C/C++ 库的基准测试感兴趣。

编辑：在这两个基准测试中，模式都是针对旧版本的 Linux Howto 进行测试的。绝大多数行没有匹配项。

关于 DFA 与 NFA：如果我是对的，纯 DFA 无法捕获组，至少不容易捕获。只有 NFA 可以捕获组。我听说RE2将本地 NFA 转换为 DFA，用于没有组捕获的正则表达式。我不知道这是不是真的。

在 PCRE 上：PCRE 与 Perl 有同样的问题——在复杂的交替中效率低下。您可以查看计算机语言基准游戏中的regex-dna 基准。使用 PCRE 的版本都比使用 TCL 的最快版本慢得多（也许 PCRE 没有使用 trie？）。V8 显然是该基准测试的赢家，因为它不使用回溯。IMO，对于 C++ 程序员来说，最好的正则表达式库是 RE2。

于 2013-06-15T00:28:50.610 回答
12

关键不是 Perl 比 Java 快还是不快（基准测试会告诉你），而是正则表达式确实（深刻）是语言本身的一部分。只是一个例子，在 Perl 中，不需要加载任何模块来使用正则表达式。请参阅此相关答案

前任。伪终端中的 Perl单行符（打印根的外壳）：

perl -nE '/^root.*:([\/\w]+)$/ and say $1' /etc/passwd

在 Java 中你需要多少行来做同样的事情？

Perl 实际上是正则表达式的参考语言。这就是为什么这么多语言使用PCRE引擎（这意味着Perl 兼容正则表达式）

于 2013-06-15T00:10:33.893 回答