提高正则表达式性能的几点实用建议汇总

目录
  • 为什么正则表达式效率很重要?
  • 低效正则表达式的剖析
  • 真实例子
  • 编写高效正则表达式的指南
    • 考虑故障场景
    • 注意通配符标记的多次重复
    • 不要以通配符重复开始正则表达式
    • 只匹配你真正需要的
    • 试着快速失败
    • Profile-尤其是故障案例
    • 尽量减少从主机中提取的数据
    • 除非绝对必要,否则不要使用组
    • 考虑正则表达式
  • TPL触发器的正则表达式优化
    • 索引
    • 试着给点提示
    • 尝试做出独特的提示
  • 总结

当正则表达式通常与大型数据集相匹配时它们的编写必须高效。

为什么正则表达式效率很重要?

虽然写得好的正则表达式可能非常有效,但写得不好的正则表达可能需要很长时间才能运行,并且会显著降低系统的速度。编写一个需要数小时或数天才能完成的正则表达式是很有可能的,甚至可以编写一个在宇宙生命周期内无法完成的正则表达,因为它是针对中等大小的字符串运行的。

在实践中已经做了一些改进,使其比以前的版本更能抵抗低效的正则表达式。它现在最小化了在决定运行哪些TPL模式时所需的正则表达式匹配。它还扩展了在多个处理器之间运行TPL模式的工作,这样,如果一个处理器忙于长正则表达式匹配,其他处理器可以继续工作。

尽管有了这些改进,编写高效的正则表达式对于保持系统发现的最佳运行仍然很重要。如果扫描网络时系统发现速度明显减慢,并且推理或发现服务长时间使用100%CPU,则一个可能的原因是效率低下的正则表达式。

低效正则表达式的剖析

那么,如何编写低效的正则表达式呢?一个问题是当正则表达式执行过度回溯时;当正则表达式中有多个重复运算符时,可能会发生这种情况。重复运算符是+*,或{n,m}。如果正则表达式进行了部分匹配,但随后失败,那么它必须返回并尝试任何其他可能的部分匹配,以防其中任何一个成功。

例如,考虑匹配正则表达式a.*b*cd对字符串abc abc abc。匹配永远不会成功,因为字符串中没有d,但正则表达式在放弃之前仍必须检查字母abc的所有可能组合。即:

"*abc* abc abc",
"*ab*c ab*c* abc",
"*ab*c abc ab*c*",
"*a*bc a*bc* abc",
"*a*bc a*b*c ab*c*",
"*a*bc abc a*bc*",
"abc *abc* abc",
"abc *ab*c ab*c*",
"abc *a*bc a*bc*",
"abc abc *abc*"

作为粗略的指导,正则表达式需要执行的比较次数与字符串长度乘以可能的中间匹配次数成比例。

在本例中,使用非贪婪运算符,即a.*?b.*?cd对匹配的数量没有影响,因为正则表达式引擎仍然需要尝试每个组合。

真实例子

让我们来看一些基于实际正则表达式的示例,这些示例在实际系统运行中造成了问题:

\b.*xx.*foo

这是一个正则表达式,与主机上的进程命令行进行比较。当运行一个半兆字节的字符串时,它失败了,该字符串包含大量的xx重复,但不包含foo

让我们来分析它与字符串匹配时发生的情况:

  • 引擎从字符串的开头开始扫描。
  • 引擎向前扫描,直到找到单词边界\b。
  • 引擎从单词边界向前扫描,直到找到匹配的xx。
  • 引擎从xx向前扫描,直到找到字符串foo或到达字符串的末尾。
  • 如果它已经到达字符串的末尾,并且不匹配foo,则它将返回到步骤3并向前扫描到下一个xx。
  • 如果它匹配了所有的xx,但仍然没有找到foo,那么它将返回到步骤2,并向前扫描到下一个单词边界。

因此正则表达式匹配包含嵌套循环;总处理时间由字符串长度(对于导致问题的命令行,该长度约为500000)乘以xx子字符串数(约500)乘以字边界数(约80000)确定。这大致相当于扫描一个20万亿字符长的字符串,需要一天多的时间才能完成。

这通过两种方式解决:

首先,是\b.*从正则表达式的开始处删除,因为它除了减慢整个过程之外没有其他用途。此更改将运行时间从几天减少到几秒。

其次,我们可以使用关于我们想要匹配的数据的知识;在这种情况下,我们只对从字符串开始到第一个空格的文本感兴趣。因此,为了停止正则表达式扫描整个字符串,我们可以将正则表达式锚定到字符串的开头,并使用\S标记匹配非空白字符。最后一个正则表达式^\S*xx\S*foo将在到达空白字符时立即停止。现在,对同一字符串运行时需要几微秒。

-A(\D+)+-B(\D+)

这被用作敏感数据过滤器。其目的是扫描命令行并删除以-A-B开头的选项。然而,它不仅没有达到作者的意图,而且它的执行方式可能永远无法处理。

让我们把它分解:

  • 从字符串开始扫描,直到找到-A
  • 匹配所有非数字字符,直到找到-B
  • 如果找不到-B,请尝试匹配-A和字符串末尾或下一个数字之间的每个组组合。例如,如果字符串的其余部分是abcd,则它将与(\D+)的以下每个组匹配+
(abcd)
(abc)(d)
(ab)(cd)
(ab)(c)(d)
(a)(b)(cd)
(a)(bc)(d)
(a)(bcd)
(a)(b)(c)(d).

对于剩余字符串中的每个附加字符,组合数将加倍。

因此,对于命令行包含-A但不后跟-B的情况,它将花费与2n成比例的时间,其中N是-A和下一个数字或字符串结尾之间的字符数。为了更好地理解这一点,在标准PC上,22个字符的字符串大约需要一秒钟。一个40个字符的字符串大约需要3天,而一个100个字符的串需要95836965945500年,尽管这尚未经过测试。

此正则表达式通过删除组重复来固定,因为它没有任何用途:

-A(\D+)-B(\D+).运行时间从永远下降到几微秒。

编写高效正则表达式的指南

本节提供了帮助您避免常见问题和编写高效正则表达式的指南。

考虑故障场景

如前面的示例所示,当正则表达式无法完全匹配,但存在多个部分匹配时,就会出现问题。编写正则表达式时,仅考虑正则表达式成功时会发生什么是不够的,还需要考虑正则表达式失败时的执行情况。实际发现中使用的正则表达式通常与大量的命令行相匹配,这些命令行可能非常长(多达一百万个字符不是未知的),并且可能包含与正则表达式部分匹配的文本,而不是全部。

注意通配符标记的多次重复

通配符标记是可以匹配多个字符的任何内容;这包括:.\w\D、字符类、否定字符类等。

如果一个正则表达式有两个或多个连续的通配符重复,则存在回溯的可能性。例如,如果目标字符串以a开头,长度为N个字符,并且不包含x,则:

  • a.*.*x - 需要N2场比赛。
  • a.*x*.*x -也需要N2个匹配,因为x*可以是零长度匹配,所以可以匹配字符串中的任何位置。
  • a.*y.*x -将取N*M个匹配,其中M是y的出现次数。

真的要当心嵌套组重复

如上所述,如果存在一个包含重复的组,并且该组本身也被重复,例如(.*),则可能的匹配数可能呈指数增长。

不要以通配符重复开始正则表达式

这是上述第二点的特例。正则表达式引擎在字符串中的任何位置搜索匹配项,因此它尝试从第一个字符开始匹配正则表达式,然后从第二个字符开始,依此类推,直到找到匹配项。*x的正则表达式等价于^.*的正则表达式*x,其遭受上述回溯问题。

由于这是一个非常常见的错误,实际发现会查找以不必要的*开头的正则表达式,并在可能的情况下将其去掉。

只匹配你真正需要的

正则表达式应设计为在有足够的匹配项时立即停止,或者知道它无法匹配。例如,考虑正则表达式\b\w+XXX*

  • \b\w+是冗余的,可以用“\w”替换。这将在原始正则表达式匹配的所有情况下匹配。
  • 末尾的.*也是多余的,因为它对匹配是否成功没有影响。

因此,整个正则表达式可以替换为\wXXX

例外情况是,您需要使用匹配的字符串,而不是简单地测试匹配是否成功

试着快速失败

如果整个正则表达式达到不可能与预期目标匹配的程度,请尝试使其失败。

上面所示的第一个真实世界示例就是一个例子。正则表达式^\S*xx\S*foo永远不会扫描超过第一个空格字符的字符串,无论它是否成功。在使用它的上下文中,这意味着扫描一个大约100个字符的序列和扫描一个数十万个字符的顺序之间的区别。

Profile-尤其是故障案例

测试正则表达式以确保它与您期望的匹配是很重要的。但是,测试与正则表达式部分匹配的长字符串(例如,随机字符的兆字节字符串)的性能也是很重要的。

尽量减少从主机中提取的数据

TPL模式允许您在主机上运行命令,并检索要用正则表达式搜索的数据,例如版本信息。

一个常见的错误是收回大量信息,例如:

cat file1 file2 file3...

然后对数据运行正则表达式以提取一条信息。

这可能会返回大量数据,因此正则表达式匹配不仅需要很长时间,而且在网络上传输数据也会很慢,并占用数据存储中的大量空间。

更好的方法是只通过在主机上运行命令(如grephead)来获取您感兴趣的信息。例如:

grep VERSION file1 file2 file3...

然后可以在返回的更短文本上运行正则表达式。

除非绝对必要,否则不要使用组

当使用括号将正则表达式的一部分括在组中时,正则表达式引擎必须做额外的工作来保存组匹配的文本,以备以后需要。在某些情况下,这可能会使匹配过程减慢四倍或更多。

如果需要使用括号,例如对于重复的正则表达式的一部分,但不需要在之后使用组的内容,则可以使用非分组版本的括号- (?:...).这通常仍然比没有括号慢,但比普通括号快。例如:

  • (abc|def) -*慢速。仅在以后需要使用匹配文本时使用。
  • (?:abc|def) - 更快
  • abc|def -最快

考虑正则表达式

虽然这些指导方针可能会有所帮助,但没有什么可以替代退一步重新检查正则表达式以提高效率和准确性所带来的思想和理解。

TPL触发器的正则表达式优化

使用正则表达式索引来提高模式性能。索引用于快速消除那些显然无法与给定字符串匹配的正则表达式。这大大减少了必须执行的正则表达式的数量。因此,推理通常可以避免执行本文档其余部分描述的病理正则表达式。

在优化TPL模式触发器的正则表达式时,有助于基本了解索引的工作方式。

索引

正则表达式由一个称为提示的属性索引。提示是不区分大小写的字符串,是与表达式匹配的每个字符串的子字符串。例如,表达式提升(后桅|主支架),ye(陆上流浪狗124坏血病狗)!它有三个明显的提示:

  • {{Hoist the }}
  • , ye "
  • !

为简单起见,每个表达式仅按其最长提示进行索引。在上面的例子中,提示将是{{提升}}。

一些正则表达式没有任何提示。例如,\d+[-/]\d++[-]\d+没有必须作为匹配字符串一部分的子字符串。提示计算器(目前)也相当幼稚,遗漏了一些可能被提取的提示。没有提示的表达式必须单独处理。

当尝试匹配字符串时,将查询索引中的一组正则表达式,其提示显示为所匹配字符串的子字符串。一旦建立,索引可以非常快地执行此查询。这个集合与一组没有提示的表达式组合在一起,形成了所有可能与字符串匹配的正则表达式的集合。尝试依次将字符串与每个表达式匹配,直到找到一个表达式或没有表达式,这意味着字符串不匹配。

试着给点提示

必须对给定给索引的每个字符串运行没有提示的正则表达式。因此,尝试使用可以计算提示的正则表达式是很重要的。

索引的提示提取算法无法处理以下类型的子表达式,将使用它们来划分提示:

  • 内置字符类,如\d、\w和。
  • 自定义字符类,如[ijkxyz]
  • 可选表达式,如?和*
  • 组,如(foo)+
  • 交替,如foo|bar

在表达式的顶层使用交替始终会阻止提取提示。组内的交替不会阻止从组外的表达式部分提取提示。

尝试做出独特的提示

如果正则表达式只有一个类似java的提示,则需要对照大量字符串进行检查。尝试设计您的表达式,使其最长的提示相当罕见。

总结

到此这篇关于提高正则表达式性能的几点实用建议的文章就介绍到这了,更多相关提高正则表达式性能内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • 正则表达式性能优化方法(高效正则表达式书写)

    这里说的正则表达式优化,主要是针对目前常用的NFA模式正则表达式,详细可以参考:正则表达式匹配解析过程探讨分析(正则表达式匹配原理).从上面例子,我们可以推断出,影响NFA类正则表达式(常见语言:GNU Emacs,Java,ergp,less,more,.NET语言, PCRE library,Perl,PHP,Python,Ruby,sed,vi )其实主要是它的"回溯",减少"回溯"次数(减少循环查找同一个字符次数),是提高性能的主要方法. 我们来看个例子:

  • 提高正则表达式性能的几点实用建议汇总

    目录 为什么正则表达式效率很重要? 低效正则表达式的剖析 真实例子 编写高效正则表达式的指南 考虑故障场景 注意通配符标记的多次重复 不要以通配符重复开始正则表达式 只匹配你真正需要的 试着快速失败 Profile-尤其是故障案例 尽量减少从主机中提取的数据 除非绝对必要,否则不要使用组 考虑正则表达式 TPL触发器的正则表达式优化 索引 试着给点提示 尝试做出独特的提示 总结 当正则表达式通常与大型数据集相匹配时它们的编写必须高效. 为什么正则表达式效率很重要? 虽然写得好的正则表达式可能非常

  • JavaScript提高网站性能优化的建议(二)

    在javascript关于提高网站性能的几点建议(一)中,从HTTP请求到页面渲染几个方面对提高网站性能提出了几点建议,本文是学习Steve Sounders的另外一本书<高性能网站建设进阶指南>之后,从JavaScript性能的角度进行总结概括,诸君共勉. JavaScript性能是实现高性能Web应用程序的关键 --Steve Sounders 1 利用js作用域链 作用域链(scope chain) 当执行一段JavaScript代码(全局代码或函数)时,JavaScript引擎会创建为

  • JavaScript关于提高网站性能的几点建议(一)

    近在学习<高性能网站建设指南>这本书,本文算是一个学习笔记,将学到的东西进行整理一下,方便后面查看. 性能黄金法则(Performance Golden Rule)解释了只有10%~20%的最终用户响应时间花在接受所请求的用户HTML文档上,剩余的80%~90%时间花在为HTML文档所引用的所有组件(图片.脚本.样式表等)进行的HTTP请求上,最终用户响应时间花费在页面组件上   --Steve Sounders 1 文件合并(减少HTTP请求数量) CSS Sprites   利用css s

  • 充分利用ASP.NET的三种缓存提高站点性能的注意方法

    ASP.NET提供三种主要形式的缓存:页面级输出缓存.用户控件级输出缓存(或称为片段缓存)和缓存API. 尽早缓存:经常缓存  您应该在应用程序的每一层都实现缓存.向数据层.业务逻辑层.UI或输出层添加缓存支持.内存现在非常便宜-因此,通过以智能的方式在整个应用程序中实现缓存,可以获得很大的性能提高. 页面级输出缓存 最简单的缓存形式,只是在内存中保留为响应请求而发送的HTML的副本. 要实现页面输出缓存,只要将一条OutputCache指令添加到页面即可. <%@ OutputCache Du

  • 提高jQuery性能优化的技巧

    下面把提高jQuery性能优化技巧给大家分享如下: 缓存变量 DOM遍历是昂贵的,所以尽量将会重用的元素缓存. 复制代码 代码如下: // 糟糕 h = $('#element').height(); $('#element').css('height',h-20); // 建议 $element = $('#element'); h = $element.height(); $element.css('height',h-20); 避免全局变量 jQuery与javascript一样,一般来说

  • SQL Server 聚焦存储过程性能优化、数据压缩和页压缩提高IO性能方法(一)

    前言 关于SQL Server基础系列尚未结束,还剩下最后一点内容未写,后面会继续.有园友询问我什么时候开始写SQL Server性能系列,估计还得等一段时间,最近工作也比较忙,但是会陆陆续续的更新SQL Server性能系列,本篇作为性能系列的基本引导,让大家尝尝鲜.在涉及到SQL Server性能优化时,我看到的有些文章就是一上来列出SQL Server的性能优化条例,根本没有弄清楚为什么这么做,当然也有可能是自己弄懂了,只是作为备忘录,但是到了我这里,我会遵循不仅仅是备忘录,还要让各位园友

  • php提高脚本性能的4个技巧

    通常,我使用明显的常规PHP函数编写代码来解决相应的问题.但是对于其中的一些问题,我遇到了一些替代解决方案,这些解决方案特别提高了性能. 在本文中,我想介绍一些替代方案.如果您正在寻找可能减少生产中执行时间的可能性,这将很有用.让我们看看,哪种PHP方法可能会被性能更高的方法所取代,以及是否存在成本或折衷的问题. 1.删除重复项 您有一个包含重复项的大型数组,并且希望删除它们,使其仅具有唯一值的数组. 常规 array_unique($array); 替代 array_keys(array_fl

  • 关于Oracle多表连接,提高效率,性能优化操作

    执行路径:ORACLE的这个功能大大地提高了SQL的执行性能并节省了内存的使用:我们发现,单表数据的统计比多表统计的速度完全是两个概念.单表统计可能只要0.02秒,但是2张表联合统计就可能要几十表了. 这是因为ORACLE只对简单的表提供高速缓冲(cache buffering) ,这个功能并不适用于多表连接查询..数据库管理员必须在init.ora中为这个区域设置合适的参数,当这个内存区域越大,就可以保留更多的语句,当然被共享的可能性也就越大了. 当你向ORACLE提交一个SQL语句,ORAC

  • android布局优化的一些实用建议

    前言 Android的绘制优化其实可以分为两个部分,即布局(UI)优化和卡顿优化,而布局优化的核心问题就是要解决因布局渲染性能不佳而导致应用卡顿的问题,所以它可以认为是卡顿优化的一个子集. 本文主要包括以下内容 为什么要进行布局优化及android绘制,布局加载原理 获取布局文件加载耗时的方法 介绍一些布局优化的手段与方法 一些常规优化手段 为什么要进行布局优化? 为什么要进行布局优化?答案是显而易见的,如果布局嵌套过深,或者其他原因导致布局渲染性能不佳,可能会导致应用卡顿 那么布局到底是如何导

  • 图片该如何优化来提高网站性能

    概述 图像是web上提供的最基本的内容类型之一.他们说一张图片胜过千言万语.但是如果你不小心的话,图片大小有时高达几十兆. 因此,虽然网络图像需要清晰明快,但它们尺寸可以缩小压缩的,使用加载时间保持在可接受的水平. 在我的网站上,我注意到我的主页的页面大小 超过了1.1MB,图片占了约88%,我还注意到我提供的图像比它们需要的大(在分辨率方面),显然,还有很多改进的空间. 我开始阅读 Addy Osmani 的优秀Essential Image Optimization电子书,并开始在我的网站上

随机推荐