Posted by & filed under 每日一题.

【四脚猫】每日一题(10月15日):某公司js大牛请假了,某phper自告奋勇的承担了js代码的工作,此时写了一个js,但遇到一个诡异的问题

  1. var matchs = /^(x+)+$/.exec(“xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxoo”);
  2. alert(matchs);

这段代码执行了超长时间长达两分钟,这是为啥?

 

参考答案:

NFA和DFA的引擎是有区别的。js/perl/php/java/.net都是NFA引擎。
而DFA与NFA机制上的不同带来5个影响:
1. DFA对于文本串里的每一个字符只需扫描一次,比较快,但特性较少;NFA要翻来覆去吃字符、吐字符,速度慢,但是特性丰富,所以反而应用广泛,当今主要的正则表达式引擎,如Perl、Ruby、Python的re模块、Java和.NET的regex库,都是NFA的。
2. 只有NFA才支持lazy和backreference(后向引用)等特性;
3. NFA急于邀功请赏,所以最左子正则式优先匹配成功,因此偶尔会错过最佳匹配结果;DFA则是“最长的左子正则式优先匹配成功”。
4. NFA缺省采用greedy量词(就是对于/.*/、/\w+/这样的“重复n”次的模式,以贪婪方式进行,尽可能匹配更多字符,直到不得以罢手为止),NFA会优先匹配量词。
5. NFA可能会陷入递归调用的陷阱而表现得性能极差。

backtracking(回朔)
当NFA发现自己吃多了,一个一个往回吐,边吐边找匹配,这个过程叫做backtracking。由于存在这个过程,在NFA匹配过程中,特别是在编写不合理的正则式匹配过程中,文本被反复扫描,效率损失是不小的。明白这个道理,对于写出高效的正则表达式很有帮助。

而对于Javascript中的正则来说, 应该是优先匹配量词, 导致了很深的递归, 形成了性能问题…

欢迎各位攻城狮,各位大牛给每日一题投稿,大家可以把自己碰到的有趣问题,工作中碰到的难题等…发送到 稿件邮箱:2313427189@qq.com