代码之家 › 专栏 › 技术社区 › Déjà vu

字符串操作与Regexps

string perl regex php java

Déjà vu · 技术社区 · 14 年前

但是,考虑到自己进行一些字符串操作的开销( 不是说算法错误-这是另一回事 PHP 或 Perl (也许吧 Java )什么是限制 ,在哪种情况下,我们可以认为字符串操作是更好的选择?什么regexp特别贪婪CPU?

例如,在 C++ Java , 菲律宾比索 或 Perl语言

regexp可能会更快:

s/abc/def/g 或者 ... while((i=index("abc",$x)>=0) ...$y .= substr()... 基于Web的解决方案?
s/(\d)+/N/g

但那你呢

一个手工制作的特定算法会不会更快(而编写的时间更长)?

问题的重点是确定哪种regexp更适合通过字符串操作针对给定问题重写?

编辑2

一个常见的实现是Perl regexp。例如,在Perl中-需要知道它们是如何实现的-什么 友善的 是否要避免使用regexp,因为它的实现会使过程变得冗长和无效?它可能不是一个复杂的regexp。。。

2011年7月编辑

我不是说所有的regexp都很慢。一些特定的regexps模式由于其特定的处理和实现而被认为是缓慢的。
例如,在最近的Perl/PHP实现中,什么是已知的相当慢的-并且应该避免的?
答案应该来自那些已经做过自己研究(profiler…)的人,他们能够提供一种关于建议/避免什么的一般指导方针。

6 回复 | 直到 4 年前

Greg Bacon 14 年前

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

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

正在做,而且 index($_, 0, 1) = ""

正则表达式的重要考虑因素不是下限,而是上限

Chas. Owens 14 年前

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

proper email validation regex 长度超过6000个字符,它甚至不能处理所有的情况(你必须首先去掉注释)。

至少在Perl5中,如果它有语法,可能不应该用一个正则表达式来解析它。

如果regex已经增长到无法再轻松维护的程度(请参阅前面的电子邮件验证示例),或者评测显示regex是代码中的慢组件,那么还应该将regex重写为自定义函数。

您似乎关心regex与自定义算法的速度,但在您使用探查器证明这一点之前,这并不是一个有效的关注点。以最易维护的方式编写代码。如果正则表达式是清晰的,那么使用正则表达式。如果自定义算法是明确的,则使用自定义算法。如果在评测代码后发现其中一个正在占用大量时间,那么就开始寻找替代方案。

Artefacto 14 年前

正则表达式永远不会比手工算法更快,因为它有着非常特殊的用途。更糟糕的是,在PHP中,它们必须在第一次使用时进行编译(之后使用缓存)。

preg_replace('/a/', 'b', $string) 几乎肯定会比在PHP中通过字符串循环更快。但这在执行时间上是一个常数惩罚,有时正则表达式,由于回溯,可能有更糟糕的渐近行为。

我们强烈建议您了解正则表达式是如何实现的,这样您就可以知道何时编写低效的正则表达式。

Steve Wortham 14 年前

然而,正则表达式速度慢的情况是 excessive backtracking occurs

通常可以重写正则表达式以获得更好的性能。但最终的性能将是为特定任务编写自己的优化解析器。例如,通过编写自己的解析器,您可以在维护内存(或状态)的同时从左到右进行解析。如果在过程代码中使用此技术,通常可以在一次过程中实现所需的效果,而不会出现回溯的缓慢情况。

今年早些时候我面临着这个决定。事实上,手头的任务甚至是在正则表达式的外围。最后,我决定编写自己的解析器,一个嵌入式下推自动机,它对我所要做的事情非常有效。顺便说一句,任务是构建一些能够解析正则表达式并为它们提供类似Intellisense的代码提示的东西。

Your Common Sense 14 年前

什么样的regexp更适合通过字符串操作专门为给定的问题重写?

容易的。

每次你问自己这样一个问题时,提醒自己在默认情况下,所有额外优化和超快速的代码都会在每个用户请求时被逐字符解析,这是非常有用的。没有破解大脑的regexp,没有狡猾的字符串操作,只是一个接一个的老好人。

Bart 14 年前

正则表达式并不慢。但是实现可能会很慢,主要是因为每次使用它们时都会对其进行解释和重新构建。但是好的regexp库允许您使用编译版本。他们跑得很快。