perl中的正则表达式比Java或其他语言更快吗？

Question

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

Answer 1

当其中一个引擎(Java)出现明显错误时,为什么还要考虑两个引擎的速度？(搜索Tom"tchrist"Christiansen关于这个主题的着作.)例如,\s无法匹配许多空格字符.

此外,一些在线文档还表示Perl在正则表达式处理方面具有优势.

这里有一些:

• 有许多功能在其他引擎中找不到,或者因为其他引擎尚未复制它们,或者因为它们的设计不允许它们支持这些功能.
• 高度优化.其中许多优化有助于更快地报告失败的匹配,许多基准未涵盖的内容.
• Unicode支持的领导者.它的支持是如此先进,以至于我们的开发人员发现了Unicode标准本身的问题,并努力让它们得到解决!
• 备注无bug.

Answer 2

你可以看看这个基准.在表格中,列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.

Answer 3

问题不在于Perl是否比Java更快(基准测试会告诉你),但是这个正则表达式确实是(深层)语言本身的一部分.举个例子,在Perl中,不需要加载任何模块来使用正则表达式.看到这个相关的答案

防爆.伪终端中的Perl 单行(打印根的shell):

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

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

Perl事实上是正则表达式的参考语言.这就是为什么这么多语言使用PCRE引擎(这意味着Perl兼容正则表达式)