js 正则学习小记之匹配字符串字面量优化篇

 更新时间:2020-05-11 14:32:22   作者:佚名   我要评论(0)

昨天在《js 正则学习小记之匹配字符串字面量》谈到 /"(?:\\.|[^"])*"/ 是个不错的表达式,因为可以满足我们的要求,所以这个表达式可用,但不一定是最好的。

昨天在《js 正则学习小记之匹配字符串字面量》谈到 /"(?:\\.|[^"])*"/ 是个不错的表达式,因为可以满足我们的要求,所以这个表达式可用,但不一定是最好的。
从性能上来说,他非常糟糕,为什么这么说呢,因为 传统型NFA引擎 遇到分支是从左往右匹配的,
所以它会用 \\. 去匹配每一个字符,发现不对后才用 [^"] 去匹配。
比如这样一个字符串: "123456\'78\"90"
16 个字符,除了第一个 " 直接匹配成功,还剩余 15 个,只有 2 个转义(4 个字符),所以 \\. 会失败 10 次,只有 2 次成功。
10 次匹配失败,需要回溯后用 [^"] 才能匹配成功,当然最后一个 " 会直接匹配成功。

很明显,正常的字符串不可能全是转义,正常的字符串才是主流,当然不排除有人故意全转义的情况。
所以这个正则需要10次回溯后才能匹配完成,如果字符串增长到 1K 1M 肿么破呢?
所以我们要修改下这个正则,前后换下位置么?
难道是 /"(?:[^"]|\\.)*"/ ? 呵呵,好像不太对,这样的话转义就不能被匹配了。

所以还要修改下 /"(?:[^"\\]|\\.)*"/ 这样就OK了,遇到 \ 转义就会用 \\. 去尝试匹配。

可是还是有问题,因为我们在 [^"\\] 过滤掉了 \n 所以没法匹配多行字符的情况。

js 中 字符串用 \ 折行是允许的,但是修改后的 正则 没法匹配这样的字符串了,所以我们还得继续修复。

因为 . 没法匹配换行,所以我们要用其他方式表达。
. 是用于匹配除换行符之外的所有字符,难道我们要 [.\n] 来表示么?
这样是不对的,因为 [] 字符集中的 . 不再表示除换行符之外的所有字符,而是字符 . 也就是他本身一个字符而已。
那怎么办呢?
其实换个思路,
\d 表示 0-9
\D 表示 [^0-9]
那么 [\d\D] 就表示所有了,不是么。(新人朋友不知道能不能消化这个知识点。)
同理 [\s\S] [\w\W] 同样可以。
所以 /"(?:[^"\\]|\\[\d\D])*"/ 这样就满足我们的要求了。

效果不错。
回头过来分分析下他现在的性能吧。
还是这个字符串: "123456\'78\"90" , 正则 /"(?:[^"\\]|\\[\d\D])*"/

16 个字符,除了第一个 " 直接匹配成功,还剩余 15 个,有 2 个转义(4 个字符),[^"\\] 能匹配成功 10 个字符,只有 2 次失败。
为什么不是 4 次失败呢,明明有4个字符啊。\\ 虽然是2个字符,但是读到第一个 \ 就匹配失败,然后用 \\[\d\D] 匹配成功,
占用掉了两个字符 \\ 下次用下一个o开始匹配,所以只有2次回溯。

只有 2 次需要回溯,然后用 \\[\d\D] 匹配成功。当然最后一个 " 还是会直接匹配成功。
所以从 10 次回溯,减少到了 2 次,虽然正则比昨天臃肿了很多,但至少性能提升了不止一个等级。

OK,今天的分享完毕,明天见。

相关文章

  • js 正则学习小记之匹配字符串字面量优化篇

    js 正则学习小记之匹配字符串字面量优化篇

    昨天在《js 正则学习小记之匹配字符串字面量》谈到 /"(?:\\.|[^"])*"/ 是个不错的表达式,因为可以满足我们的要求,所以这个表达式可用,但不一定是最好的。
    2020-05-11
  • js正则学习小记之匹配字符串字面量

    js正则学习小记之匹配字符串字面量

    今天看了第5章几个例子,有点收获,记录下来当作回顾也当作分享。 关于匹配字符串问题,有很多种类型,今天讨论 js 代码里的字符串匹配。(因为我想学完之后写个语法
    2020-05-11
  • Python正则表达式指南 推荐

    Python正则表达式指南 推荐

    本文介绍了Python对于正则表达式的支持,包括正则表达式基础以及Python正则表达式标准库的完整介绍及使用示例。本文的内容不包括如何编写高效的正则表达式、如何优化
    2020-05-11
  • JavaScript正则表达式匹配字符串字面量

    JavaScript正则表达式匹配字符串字面量

    第一次遇到这个问题, 是大概两年前写代码高亮, 从当时的解决方案到现在一共有三代, 嘎嘎. 觉得还是算越来越好的. 第一代: //那个时候自己正则还不算很精通, 也没有
    2020-05-11
  • linux grep不区分大小写查找字符串方法

    linux grep不区分大小写查找字符串方法

    grep用来过滤字符串信息,grep默认对字母大小写敏感,不过可以通过选项对grep屏蔽大小写敏感,该选项为 -i。 一、查看grep工具版本方法 图1 grep版本查询 二、grep
    2020-05-11
  • 55分钟学会正则表达式(来自Github)

    55分钟学会正则表达式(来自Github)

    55分钟学会正则表达式 http://qntm.org/files/re/re.html 翻译水平有限,如有谬误,欢迎评论斧正或者Pull Request。 荐几个正则表达式编辑器 Debuggex :https:/
    2020-05-11
  • 解析正则表达式中的.*,.*?,.+?的含义

    解析正则表达式中的.*,.*?,.+?的含义

    1. .* . 表示匹配除换行符 \n 之外的任何单字符,*表示零次或多次。所以.*在一起就表示任意字符出现零次或多次。没有?表示贪婪模式。比如a.*b,它将会匹配最长的
    2020-05-11
  • 正则表达式替换table表格中的样式与空标记(保留rowspan与colspan)

    正则表达式替换table表格中的样式与空标记(保留rowspan与colspan)

    完整测试代码 <script> var str='<p>'; str='<table id="tblSort" cellspacing="0" helvetica="" sans=""><tr id="sdf"><td style="color:red" class="ok&qu
    2020-05-11
  • 使用vue cli4.x搭建vue项目的过程详解

    使用vue cli4.x搭建vue项目的过程详解

    cli-4.x已经发布好久了,斟酌了好久,还是决定将原来的cli-2.x升级到4.x,详细的升级过程可以戳这里 1、创建项目 vue create vuetest 2、选择配置方式 &#63; Pl
    2020-05-08
  • 基于JQuery实现页面定时弹出广告

    基于JQuery实现页面定时弹出广告

    Js相关技术 定时器: &#8203; setInterval & clearInterval &#8203; setTimeout & clearTimeout 显示: img.style.display = "block" 隐藏: img.style.d
    2020-05-08

最新评论