从 trim 原型函数看 JS 正则表达式的性能

问题

一般情况下用正则写法为:

<script type="text/javascript">//<![CDATA[
  String.prototype.trim = function () {
    return this.replace(/^[\s\t ]+|[\s\t ]+$/g, '');
  }
  s = ' rank\'s weblog, www.rank.im ';
  alert(s.trim().length);
//]]></script>

如果遇到大数据的变长字符串的话就会发现这个是很耗资源的。
效率并不高,有的时候甚至无法忍受。

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
 <head>
 <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
 <title>rank's html</title>
 <meta http-equiv="Pragma" content="no-cache" /> 
 </head>
  <body>
  <textarea>请在这里写足够多的空格或者 tab 字符。</textarea>
  <script type="text/javascript">//<![CDATA[
  String.prototype.trim = function () {
    return this.replace(/^[\s\t ]+|[\s\t ]+$/g, '');
  }
  var s = document.getElementsByTagName('textarea')[0].value
  var d = new Date();
  s.trim();
  alert(new Date()-d);
//]]></script>
  </body>
</html>

DFA

在解释这个原因的时候想起以前看到 《 Master regular expression 》 里面有提到过。

NFA 和 DFA 引擎是有区别的。

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 可能会陷入递归调用的陷阱而表现得性能极差。

JS 是 NFA 引擎。

backtracking (回朔)

当 NFA 发现自己吃多了,一个一个往回吐,边吐边找匹配,这个过程叫做 backtracking 。

由于存在这个过程,在 NFA 匹配过程中,特别是在编写不合理的正则式匹配过程中,文本被反复扫描,效率损失是不小的。明白这个道理,对于写出高效的正则表达式很有帮助。

定位/分析原因

在解释上面的 trim 原型方法的时候。
经过测试,有几个方法是可以化解 JS NFA 引擎的回朔次数:

  • 去掉限定的量词,即改成

     String.prototype.trim = function () {
        return this.replace(/^[\s\t ]+|[\s\t ]$/g, '');
     }
    
    
  • 去掉字符串尾匹配。

     String.prototype.trim = function () {
        return this.replace(/^[\s\t ]+/g, '');
     }
    	
    
  • 加入多行匹配。

    String.prototype.trim = function () {
        return this.replace(/^[\s\t ]+|[\s\t ]+$/mg, '');
     }
    	
    

从以上三种改法结合文中开头的 NFA 资料,我们可以大概的知道 trim 性能出现问题的原因

  • 量词限定将优先匹配。
  • 量词限定在结尾可能会使 JS 的正则引擎不停的回朔,出现递归的一个陷阱,这个递归的深度太深。如果字符串更大一点应该会出现栈溢出了。
  • 多行既然能够匹配,而且性能消耗不大。性能上没有任何问题,从一个写这个正则程序的人角度上去看,多行明显比单行要替换的空串多得多。所以第二点的结论应该是对的。

改良 trim 函数

首先确定匹配字符串的开始正则是没有任何效率问题的。而匹配结束的时候会出现性能问题,那可以采用正则与传统相结合来改善这个 trim 性能问题。

  String.prototype.trim = function () {
    var s = this.replace(/^[\s\t ]+/g, '');
    从 s 后端开始查找,并回循环到最后一个非空字符串,代码略。
  }

-- EOF --

Comments