未古其人

目录

记一次对正则表示的效率调试

某个项目,写了如下的正则表达式

input = input.replace(/\/((.|\s){1,})\//g, "<em>$1</em>");

本来上面的代码非常简单,基本也不会出什么问题,然后当有一次遇到下面的测试时,出问题了。

简单来说,就是在一个几万字的输入文本中含有类似http://domain.com/actionName/value这样的域名时,文本的解析时间会长达近半分钟,甚至一度让我以为陷入了死循环,去检查 正则表达式是否写错了。

虽然网络应用网络传输可能就不止半分钟的时间,所以这点时间消耗最终应该不会成为最影响结果的问题,但这消耗的时间还是让人非常介意。
毕竟半分钟对现代程序和现代硬件来说,是个非常长的时间了。在正常情况下,一般都可以秒级,甚至毫秒、微妙级的单位内完成处理。这半分钟的时间算什么?

但是,作为效率控和追求问题的好奇之心,不禁要问,问题出在哪里?

于是开始慢慢调查原因。

在排除了正则表达式自身错误之后,就开始着手对文本内容的分析,开始判断究竟是什么原因导致这种奇怪的问题。
但是文本的量非常大,二分,乃至三分法也不能马上找到出问题的地方。几次查找都找不到为什么会发生问题之后,决定回到原点,再重别的思路查找一边。

而最初出问题的地方是 input.replace(/\/((.|\s){1,})\//g, "<em>$1</em>"); 这样一句正则表达式。
上面这句正则表达式意思就是说,遇到 // 之间的文本,全部算成斜体字,并且输出为斜体字。
也就是说,在对 / 进行判断的时候,哪里出了问题,导致效率急剧下降。

在不管尝试和 Google 之后,终于找到了原因,或者说出问题的文本是——https://example.com/action/value

简单来说,因为正则表达式的判断规则是不断匹配,直到文本结束或者规则结束处。

而我这里写的这个正则表达式,在对域名中的 / 进行匹配时,首先会去匹配 http: 之后的那个 /,然后一个个字符开始查找,直到找到 /

然后正则表达式中的((.|\s){1,}) 存在,所以会忽略 http: 之后的第二个 ``/,直接匹配到 action 之前的那个 /,目前到这里,一切正常。

然后,当开始匹配与 value 之前的 / 匹配的 / 时,就出现了问题,因为当时测试的文本中,并没有第四个 / 。 在这个时候,正则表达式要确认是否有匹配,就需要继续搜索,直到文本结束。而每搜索到一个文本,都需要进行判断,一来二去,时间就暴增,这就是这次效率问题的原因。

到底是什么原因呢?
因为这里我输入了一个域名,而域名中的 / 数量是最少零个,无上限(正则化的表达方式是:{0,},或者*)。
所以要特别针对域名来进行专门处理,那是不可能的。而除了域名之外,又有什么其他的表达形式,也不是我所能在正则表达式的范围内所能枚举完毕的。

然后,解决方案就有了。就当前来说,最好的方法就是让正则表达式认为目前的那个字符不认为是所要进行处理的字幕,即对文本字符进行转义。