字符串操作与Regexps

Question

我们经常被告知Regexps很慢,应该尽可能避免.

但是,考虑到自己做一些字符串操作的开销(不是谈论算法错误 - 这是另一回事),特别是在PHP或Perl(可能Java)是什么限制,在这种情况下我们可以认为字符串操作是更好的替代？什么regexp特别是CPU贪心？

例如,对于下面的C++,Java,PHP或者Perl,你会怎么推荐

正则表达式可能会更快:

• s/abc/def/g还是... while((i=index("abc",$x)>=0) ...$y .= substr()...基于解决方案？
• s/(\d)+/N/g 或扫描算法

但是关于

• 电子邮件验证regexp？
• s/((0|\w)+?[xy]*[^xy]){2,7}/u/g

手工和特定算法不会更快(写入时间更长)？

编辑

问题的关键是要确定哪种regexp最好通过字符串操作专门针对给定问题重写？

EDIT2

一个常见的实现是Perl regexp.例如在Perl -需要知道它们是如何实现的-什么样的正则表达式的是要避免的,因为实现将使过程冗长和无效？它可能不是一个复杂的正则表达式......

编辑2011年7月(根据评论)

我并不是说所有正则表达式都很慢.已知一些特定的正则表达式模式是缓慢的,这是由于它们的特定处理以及由于它们的实现.
例如,在最近的Perl/PHP实现中,已知的是相当缓慢 - 应该避免？
答案是从那些已经进行了自己的研究(剖析器......)的人那里得到的,他们能够提供一些关于建议/要避免什么的一般指导.

Answer 1

谁说正则表达速度很慢？至少在Perl中,它们往往是操纵字符串的首选方法.

正则表达式在电子邮件验证等方面很糟糕,因为主题过于复杂,而不是因为它们很慢.一个恰当的电子邮件验证的正则表达式是超过6000个字符长,它甚至不处理所有的情况下,(你必须先去掉注释).

至少在Perl 5中,如果它有一个语法,它可能不应该用一个正则表达式进行解析.

如果正则表达式已经发展到无法再轻松维护的程度(请参阅上一个电子邮件验证示例),或者性能分析显示正则表达式是代码的慢速组件,您还应该将正则表达式重写为自定义函数.

您似乎关注正则表达式与自定义算法的速度,但在您证明它与分析器一起使用之前,这不是一个有效的问题.以最易维护的方式编写代码.如果正则表达式是明确的,那么使用正则表达式.如果清除自定义算法,则使用自定义算法.如果您发现在分析代码后要么花费大量时间,那么就要开始寻找替代方案.

Answer 2

使用正则表达式操作文本的一个很好的特性是模式是高级的和声明性的.这为实现留下了相当大的优化空间,例如分解最长的公共前缀或使用Boyer-Moore来表示静态字符串.简洁的符号使专家更快地阅读.我立刻明白了什么

if (s/^(.)//) {
  ...
}

正在做,index($_, 0, 1) = ""相比之下看起来很吵.

正则表达式的重要考虑因素不是下限,而是上限.它是一个强大的工具,因此人们相信它能够从XML,电子邮件地址或C++程序中正确提取令牌,并且没有意识到需要一个更强大的工具,如解析器.