推荐关注
› Meteor
› JSLint - a JavaScript code quality tool
› jsFiddle
› D3.js
› WebStorm
推荐书目
› JavaScript 权威指南第 5 版
› Closure: The Definitive Guide
› Closure: The Definitive Guide
求解该正则表达式是如何浪费浏览器的时间的（匹配不可能成功的）： http://jsfiddle.net/ioioio/F2zQP/2/
jakwings · 2014-02-20 22:51:58 +08:00 · 3177 次点击这是一个创建于 3933 天前的主题，其中的信息可能已经有所发展或是发生改变。
Safari 的正则引擎竟然如此不同，正常通过？Chrome 和 Firefox 的正则引擎到底干了什么好事？
假如是 NFA 类型的正则引擎，匹配的时间复杂度不是应该为 O(n^2) 的么？
假如是 NFA 类型的正则引擎，匹配的时间复杂度不是应该为 O(n^2) 的么？
第 1 条附言 · 2014-02-21 00:26:22 +08:00
貌似已解决，原因见 8 楼。
 |
1
momou 2014-02-20 23:50:19 +08:00
不要用直接量语法试一下
|
 |
2
jakwings OP @momou 改成 /^ {4}[^\n]*(?:\n {4}[^\n]*\n?)*$/ 倒是很快的。但是就是不明白为什么原来的会那么慢（Safari 除外）……
|
 |
4
zzNucker 2014-02-21 00:08:22 +08:00  1
没那么简单，典型的回溯失控。 你最后的那个末尾匹配符匹配不到的话会从后往前反复逐个匹配，加上前面你的空格又只匹配掉4个，后面就有一大堆字符等着你去反复比较。。。
|
|
5
zzNucker 2014-02-21 00:09:22 +08:00
你可以试试把4改大一点或者把末尾匹配去掉。。。
|
|
6
momou 2014-02-21 00:11:35 +08:00
var regex = new RegExp("/^(?: {4}[^\n]*\n?)+$/");不会有问题
应该是字符被转义了吧 |
|
8
jakwings OP @zzNucker 呃，我好像明白了，时间复杂度似乎比 O(n^2) 还高……
重复匹配本身的复杂度就是 O(n^2) ，然后它的每一次重复中的子匹配过程也是 O(n^2) 复杂度，于是复杂度是 O(n^4) ……看来 Safari 的正则引擎干了一些特别的预测。囧 |
 |
10
lyric 2014-02-21 03:09:25 +08:00 1
大多数动态语言的正则引擎实现为了支持向后引用，都超过了正则文法，因此都不是 NFA 实现
详情可以参考这篇 Paper： http://swtch.com/~rsc/regexp/regexp1.html |
 |
11
baocaixiong 2014-02-21 17:35:01 +08:00
一不小心输入了100，浏览器挂了。。。。。
|
|
12
baocaixiong 2014-02-21 17:35:46 +08:00
cpu都跑满了。。。
|
Select Language