位置：首页>> 网络编程>> JavaScript>> 从trim原型函数看js正则表达式的性能

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

作者：Rank　来源：never-online　发布时间：2008-12-11 13:55:00　

标签：trim,函数,正则表达式,js

如果你看到别人写trim函数是用循环而不用正则表达式来写，请不要取笑，也许，他们就是高手。如果你很自信你的trim函数效率很高，请看完本文再下结论。

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

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

<!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>www.aspxhome.com</title> <meta http-equiv="Pragma" content="no-cache" /> <meta http-equiv="Cache-Control" content="no-cache" /> <meta http-equiv="Expires" content="0" /> <meta http-equiv="ImageToolbar" content="no" /> <style type="text/css" title="default" media="screen"> /*<![CDATA[*/ /*]]>*/ </style> </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>

在解释这个原因的时候想起以前看到master regular expression里面有提到过。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匹配过程中，特别是在编写不合理的正则式匹配过程中，文本被反复扫描，效率损失是不小的。明白这个道理，对于写出高效的正则表达式很有帮助。

2 下一页

投稿

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

猜你喜欢