正则表达式优化
正则表达式优化
——《精通正则表达式》阅读笔记
[TOC]
第4章:表达式的匹配原理
引擎
DFA (Deterministic Finite Automaton 确定有穷自动机):
常见的只有MySQL,文本主导,不支持反向引用和捕获括号,但快
传统型 NFA(Non-非):
大多数语言,表达式主导,编译快,内存少,写法不同有性能差异
标准 POSIX NFA:
leftmost-longest,尝试所有确保最长
混合 Tcl 等:
Perl、Python、Go(leftmost-first)
规则
最左优先,尽可能多(匹配优先)
回溯
NFA 有两个可能时会根据 匹配优先*
还是 忽略优先*?
走其中一个分支,并保存备用状态
如果不成功再回溯尝试另一个分支
第5章:正则表达式实用技巧
(多选|分支)排序可能影响匹配结果
第6章:打造高效正则表达式
减少测试和回溯
- 如果顺序不影响结果时更多匹配的放前面
- 编译
- 传动(从第1个字符开始,从第2个字符开始...)
- 检测(相连 量词{m,n}+* (捕获))
- 成功/->2.传动
- 失败
常见措施
编译优化
- 缓存
传动优化
- 锚点(行始
^ \A
起始\G
行末$ \Z \z
) - 隐式锚点(
.* .+
开始) - 开始字符
====
比={4}
快100倍 - 内嵌字符(Boyer-Moore字符串检索算法后前移, 需要前面固定个数)
- 长度小于时不运行
正则优化
- 连接当做整体
-
.*
特殊优化比(?:.)*
快(Java 10% Python 50倍) - 消除没必要的括号
- 消除没必要的[字符组]
- 忽略优先量词
*?
(尽可能少)通常比匹配优先量词慢 - 限制回溯,避免括号内外都是量词
- 避免指数级(超线性)匹配
- 使用占有优先量词(+不会回溯)减少状态
-
\d{4}
量词优化比\d\d\d\d
快(Java 几倍 Python 20%) - 引擎识别捕获括号是否需要
诀窍
-
xx*
比x+
能适应的优化更多 - 手工模拟优化
-
(000|999)$
比关闭结束锚点优化的(?:000|999)$
快(Perl 几千倍) - 避免重新编译,Perl避免用变量插值
- 使用(?:非捕获型括号)
- 不要滥用括号,如上面的
.*
比(?:.)*
快 - 不要滥用字符组,
[.]
应该用\.
- 不区分大小写效率低已经修正
- 使用起始锚点
.*
开头的前面加^
或\A
- 从量词中提取:
xx*
替代x*
,-----{0,2}
替代-{5,7}
- 提取开头:
th(is|at)
替代(this|that)
- 将锚点独立出来:
^(?:abc|123)
替代^abc|^123
,^(abc)
替代(^abc)
- 末尾独立出
$
- 接近开头忽略优先
*?
,接近结尾匹配优先 - 拆分成多个正则
- 使用(?>固化分组)和占有优先量词
*+
- 最可能匹配的分支放前面(POSIX 会全部尝试取最长就不需要)
- 结尾部分分散到各个部分(有些系统不需要如Perl的
$
)
消除循环
"(\\.|[^\\"]+)*" 优化为: "[^\\"]*(\\.[^\\"]*)*" 公式: opening normal* (special normal*) closing 左 常规*(特殊 常规*)* 右
- 常规和特殊的开头不能重合
- 特殊部分必须匹配至少一个字符
- 特殊部分必须是固化的
方法2:[^\\"]
匹配更多,如果是转义,后面继续,结果一样
方法3:匹配主机名
[a-z]+(\.[a-z]+)*
使用占有优先量词
"([^\\"]++|\\.)*+"
使用固化分组
"(?>(?>[^\\"]+|\\.)*)" \G(?:^|,)(?:((?>[^"]*)(?>""[^"]*)*)|([^",]*))
消除注释
/\*.*?\*/ /\*([^*]|\*+[^/*])*\*+/ 消除循环 /\*[^*]*\*+(?:[^/*][^*]*\*+)*/
流畅运转
块注释=/\*[^*]*\*+(?:[^/*][^*]*\*+)*/ 行注释=//[^\n]* 双引号="[^\\"]*(\\.[^\\"]*)*" 单引号='[^\\']*(\\.[^\\']*)*' (双引号|单引号)|块注释|行注释 替换为 $1 优化为: 开头集=[^"'/] (双引号|单引号|开头集+)|块注释|行注释 优化为: (开头集+|双引号|单引号)|块注释|行注释 优化为: (开头集+|双引号 开头集*|单引号 开头集*)|块注释|行注释
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
Linux 安装python3.7.4
我这里使用的分配的专用ECS,系统本身默认安装有python2.x,版本x根据不同版本有 所不同,可通过 python --V 或 python --version 查看系统自带的python版本,有一些系统命令时需要用到python2,不能卸载! 1、安装依赖包 1)首先安装gcc编译器,gcc有些系统版本已经默认安装,通过 gcc --version 查看,没安装的先安装gcc,yum -y install gcc 2)安装其它依赖包,(注:不要缺少,否则有可能安装python出错,python3.7.4以下的版本可不装 libffi-devel ) yum -y install zlib-devel bzip2-devel openssl-devel ncurses-devel sqlite-devel readline-devel tk-devel gdbm-devel db4-devel libpcap-devel xz-devel libffi-devel 2、下载python3.7.4源码,根据需求下载 1)在https://www.python.org/download...
- 下一篇
你知道Java方法能定义多少个参数吗?
一:为什么研究这么无聊的问题 这两天在读一本老书《Orange'S 一个操作系统的实现》,把丢了很长时间没研究的操作系统又重新拾起来了,在第三章讲解“保护模式”时,作者提到了调用门描述符中的Param Count只有5位,也就是说,最多只支持32个参数,这本来只是一个不是特别重要的细节,但是却勾起了我的思索:在JVM中,一个Java方法,最多能定义多少参数呢?我知道这是一个很无聊的问题,即使能定义一万个,十万个,谁又会真的去这么做呢。但是作为一个Coder,最重要的不就是好奇心吗,没有好奇心,和一条咸鱼又有什么区别呢? 二:实地考察 这种问题,第一步当然就是看看JVM中关于方法的定义,这里以openJDK10中的HotSpot为例。在ConstMethod中,代表参数数量的字段为_size_of_parameters。 u2 _size_of_parameters; // size of the parameter block (receiver + arguments) in words _size_of_parameters的类型为u2,在JVM中,u2为2个字节长,那么理论上来说...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- 设置Eclipse缩进为4个空格,增强代码规范
- CentOS6,CentOS7官方镜像安装Oracle11G
- SpringBoot2整合Thymeleaf,官方推荐html解决方案
- CentOS7编译安装Cmake3.16.3,解决mysql等软件编译问题
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- SpringBoot2全家桶,快速入门学习开发网站教程
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- CentOS7,CentOS8安装Elasticsearch6.8.6
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- MySQL8.0.19开启GTID主从同步CentOS8