一个正则式引发的血案

关于作者:Vlad Mihalcea是一个专注于软件集成,高可扩展性和并发编程挑战的软件架构师

我从来没有想到我可以看到一个差劲的正则式造成一台服务器没有响应。但它偏偏就在我们的一个服务器上面发生了,结果导致了它毫无响应。

假设我们在解析一些外部汽车经销商的信息。我们想在各种各样的输入中找到那些带”no air conditioning”的汽车,同时不要匹配那些诸如”mono air conditioning”的模式。

那个搞挂我们服务器的正则式类似于这样:

    String TEST_VALUE = "ABS, traction control, front and side airbags, 
    Isofix child seat anchor points, no air conditioning, electric windows,
     \r\nelectrically operated door mirrors";

    double start = System.nanoTime();
    Pattern pattern = Pattern.compile("^(?:.*?(?:\\s|,)+)*no\\s+air\\s+conditioning.*$");
    assertTrue(pattern.matcher(TEST_VALUE).matches());
    double end = System.nanoTime();
    LOGGER.info("Took {} micros", (end - start) / (1000 ));

两分钟后,这个测试还没有停止并且一个CPU核已经满负载运行了。

负载情况

首先,我们是在整个输入数据上使用matches方法的,所以不需要开始(^)和结束($)匹配符。其次,由于输入字符串中存在换行符,我们必须让正则式运行在多行模式下:

Pattern pattern = Pattern.compile("(?:.*?(?:\\s|,)+)*no\\s+air\\s+conditioning.*?", Pattern.MULTILINE);

让我们看一看不同版本的正则式的行为:

正则式 运行时间(毫秒) 评价
“(?:.*?(?:\\s|,)+)*no\\s+air\\s+conditioning.*?” 35699.334 这个方法等的花儿都谢了。
“(?:.*?(?:\\s|,)+)?no\\s+air\\s+conditioning.*?” 108.686 非捕获组不需要*量词(原文是+,作者应该写错了吧),所以我们用?量词代替。
“(?:.*?\\b)?no\\s+air\\s+conditioning.*?” 153.636 上一个方法只是匹配了用空白字符(\s)或逗号(,)分割输入数据的情况,这个方法适用于更多的情况。
“\\bno\\s+air\\s+conditioning” 78.831 Find比起matches更快,并且我们只对这个模式第一次出现的地方感兴趣。

为什么不用String.indexOf()

尽管它应该比正则式快很多,但我们仍需要考虑字符串开始的情况,例如一些像”mono air conditioning”的模式;以及用制表符或多个空格符分开的输入。像这样自定制的实现可能会快一些,但都缺少灵活性而且需要更多的时间去实现。

结论

正则式是模式匹配的利器,但你不应该随心所欲的使用它。因为很小的改变可能带来很大的不同。第一个正则式事与愿违的原因是由于catastrophic backtracking。这是一个每位开发者在写正则式之前都应当注意的一个现象。

原文链接: vladmihalcea 翻译: ImportNew.com - keywords
译文链接: http://www.importnew.com/10308.html
[ 转载请保留原文出处、译者和译文链接。]

关于作者: keywords

(新浪微博:@yihengw

查看keywords的更多文章 >>



相关文章

发表评论

Comment form

(*) 表示必填项

还没有评论。

跳到底部
返回顶部