V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐关注
Meteor
JSLint - a JavaScript code quality tool
jsFiddle
D3.js
WebStorm
推荐书目
JavaScript 权威指南第 5 版
Closure: The Definitive Guide
jakwings
V2EX  ›  JavaScript

求解该正则表达式是如何浪费浏览器的时间的(匹配不可能成功的): http://jsfiddle.net/ioioio/F2zQP/2/

  •  
  •   jakwings · 2014-02-20 22:51:58 +08:00 · 3060 次点击
    这是一个创建于 3690 天前的主题,其中的信息可能已经有所发展或是发生改变。
    Safari 的正则引擎竟然如此不同,正常通过?Chrome 和 Firefox 的正则引擎到底干了什么好事?

    假如是 NFA 类型的正则引擎,匹配的时间复杂度不是应该为 O(n^2) 的么?
    第 1 条附言  ·  2014-02-21 00:26:22 +08:00
    貌似已解决,原因见 8 楼。
    13 条回复    1970-01-01 08:00:00 +08:00
    momou
        1
    momou  
       2014-02-20 23:50:19 +08:00
    不要用直接量语法试一下
    jakwings
        2
    jakwings  
    OP
       2014-02-21 00:05:13 +08:00
    @momou 改成 /^ {4}[^\n]*(?:\n {4}[^\n]*\n?)*$/ 倒是很快的。但是就是不明白为什么原来的会那么慢(Safari 除外)……
    jakwings
        3
    jakwings  
    OP
       2014-02-21 00:06:30 +08:00
    @jakwings 说错了,改成 /^ {4}[^\n]*(?:\n {4}[^\n]*)*\n?$/ 才是等效的。
    zzNucker
        4
    zzNucker  
       2014-02-21 00:08:22 +08:00   ❤️ 1
    没那么简单,典型的回溯失控。 你最后的那个末尾匹配符匹配不到的话会从后往前反复逐个匹配,加上前面你的空格又只匹配掉4个,后面就有一大堆字符等着你去反复比较。。。
    zzNucker
        5
    zzNucker  
       2014-02-21 00:09:22 +08:00
    你可以试试把4改大一点或者把末尾匹配去掉。。。
    momou
        6
    momou  
       2014-02-21 00:11:35 +08:00
    var regex = new RegExp("/^(?: {4}[^\n]*\n?)+$/");不会有问题
    应该是字符被转义了吧
    zzNucker
        7
    zzNucker  
       2014-02-21 00:18:20 +08:00
    @momou new regexp 里面不要加定界符了。
    jakwings
        8
    jakwings  
    OP
       2014-02-21 00:19:39 +08:00
    @zzNucker 呃,我好像明白了,时间复杂度似乎比 O(n^2) 还高……

    重复匹配本身的复杂度就是 O(n^2) ,然后它的每一次重复中的子匹配过程也是 O(n^2) 复杂度,于是复杂度是 O(n^4) ……看来 Safari 的正则引擎干了一些特别的预测。囧
    zzNucker
        9
    zzNucker  
       2014-02-21 00:22:55 +08:00
    @jakwings 对,尤其像你这种里面又有局部能匹配的,最后又整体不能成功的,就在里面反复找来找去,非常耗时间。
    lyric
        10
    lyric  
       2014-02-21 03:09:25 +08:00   ❤️ 1
    大多数动态语言的正则引擎实现为了支持向后引用,都超过了正则文法,因此都不是 NFA 实现

    详情可以参考这篇 Paper: http://swtch.com/~rsc/regexp/regexp1.html
    baocaixiong
        11
    baocaixiong  
       2014-02-21 17:35:01 +08:00
    一不小心输入了100,浏览器挂了。。。。。
    baocaixiong
        12
    baocaixiong  
       2014-02-21 17:35:46 +08:00
    cpu都跑满了。。。
    jakwings
        13
    jakwings  
    OP
       2014-02-22 11:25:41 +08:00
    @lyric 谢了,那个大神的文章很不错~实在是值得收藏啊。

    文章里的正则测试 Chrome 还是得用好几秒,Safari 和 Firefox 都瞬间搞定了,看来 Chrome 的正则引擎的优化还不怎么聪明。Safari 的貌似是优化得最好的。Firefox 的「优化」则往往是直接抛出 InternalError ……
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2829 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 14:59 · PVG 22:59 · LAX 07:59 · JFK 10:59
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.