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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

推荐关注

› Meteor

› JSLint - a JavaScript code quality tool

› jsFiddle

› D3.js

› WebStorm

推荐书目

› JavaScript 权威指南第 5 版

› Closure: The Definitive Guide

这是一个创建于 3920 天前的主题，其中的信息可能已经有所发展或是发生改变。

Safari 的正则引擎竟然如此不同，正常通过？Chrome 和 Firefox 的正则引擎到底干了什么好事？

假如是 NFA 类型的正则引擎，匹配的时间复杂度不是应该为 O(n^2) 的么？

第 1 条附言 · 2014-02-21 00:26:22 +08:00

貌似已解决，原因见 8 楼。

匹配

复杂度

NFA

13 条回复 • 1970-01-01 08:00:00 +08:00

momou

2014-02-20 23:50:19 +08:00

不要用直接量语法试一下

jakwings

2014-02-21 00:05:13 +08:00

@momou 改成 /^ {4}[^\n]*(?:\n {4}[^\n]*\n?)*$/ 倒是很快的。但是就是不明白为什么原来的会那么慢（Safari 除外）……

jakwings

2014-02-21 00:06:30 +08:00

@jakwings 说错了，改成 /^ {4}[^\n]*(?:\n {4}[^\n]*)*\n?$/ 才是等效的。

zzNucker

2014-02-21 00:08:22 +08:00

没那么简单，典型的回溯失控。你最后的那个末尾匹配符匹配不到的话会从后往前反复逐个匹配，加上前面你的空格又只匹配掉4个，后面就有一大堆字符等着你去反复比较。。。

zzNucker

2014-02-21 00:09:22 +08:00

你可以试试把4改大一点或者把末尾匹配去掉。。。

momou

2014-02-21 00:11:35 +08:00

var regex = new RegExp("/^(?: {4}[^\n]*\n?)+$/");不会有问题
应该是字符被转义了吧

zzNucker

2014-02-21 00:18:20 +08:00

@momou new regexp 里面不要加定界符了。

jakwings

2014-02-21 00:19:39 +08:00

@zzNucker 呃，我好像明白了，时间复杂度似乎比 O(n^2) 还高……

重复匹配本身的复杂度就是 O(n^2) ，然后它的每一次重复中的子匹配过程也是 O(n^2) 复杂度，于是复杂度是 O(n^4) ……看来 Safari 的正则引擎干了一些特别的预测。囧

zzNucker

2014-02-21 00:22:55 +08:00

@jakwings 对，尤其像你这种里面又有局部能匹配的，最后又整体不能成功的，就在里面反复找来找去，非常耗时间。

lyric

2014-02-21 03:09:25 +08:00

大多数动态语言的正则引擎实现为了支持向后引用，都超过了正则文法，因此都不是 NFA 实现

详情可以参考这篇 Paper： http://swtch.com/~rsc/regexp/regexp1.html

baocaixiong

2014-02-21 17:35:01 +08:00

一不小心输入了100，浏览器挂了。。。。。

baocaixiong

2014-02-21 17:35:46 +08:00

cpu都跑满了。。。

jakwings

2014-02-22 11:25:41 +08:00

@lyric 谢了，那个大神的文章很不错～实在是值得收藏啊。

文章里的正则测试 Chrome 还是得用好几秒，Safari 和 Firefox 都瞬间搞定了，看来 Chrome 的正则引擎的优化还不怎么聪明。Safari 的貌似是优化得最好的。Firefox 的「优化」则往往是直接抛出 InternalError ……