trim原型函數(shù)看js正則表達式的性能
更新時間:2008年12月10日 18:07:47 作者:
如果你看到別人寫trim函數(shù)是用循環(huán)而不用正則表達式來寫,請不要取笑,也許,他們就是高手。如果你很自信你的trim函數(shù)效率很高,請看完本文再下結(jié)論。
一般情況下用正則寫法為:
[Ctrl+A 全選 注:引入外部Js需再刷新一下頁面才能執(zhí)行]
如果遇到大數(shù)據(jù)的變長字符串的話就會發(fā)現(xiàn)這個是很耗資源的。效率并不高,有的時候甚至無法忍受。
在解釋這個原因的時候想起以前看到master regular expression里面有提到過。NFA和DFA的引擎是有區(qū)別的。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急于邀功請賞,所以最左子正則式優(yōu)先匹配成功,因此偶爾會錯過最佳匹配結(jié)果;DFA則是“最長的左子正則式優(yōu)先匹配成功”。
4. NFA缺省采用greedy量詞(就是對于/.*/、/\w+/這樣的“重復n”次的模式,以貪婪方式進行,盡可能匹配更多字符,直到不得以罷手為止),NFA會優(yōu)先匹配量詞。
5. NFA可能會陷入遞歸調(diào)用的陷阱而表現(xiàn)得性能極差。
backtracking(回朔)
當NFA發(fā)現(xiàn)自己吃多了,一個一個往回吐,邊吐邊找匹配,這個過程叫做backtracking。由于存在這個過程,在NFA匹配過程中,特別是在編寫不合理的正則式匹配過程中,文本被反復掃描,效率損失是不小的。明白這個道理,對于寫出高效的正則表達式很有幫助。
定位/分析原因
在解釋上面的trim原型方法的時候。經(jīng)過測試,先不說結(jié)果是否正確,有幾個方法是可以化解JS NFA引擎的回朔次數(shù)的
a. 去掉限定的量詞,即改成
String.prototype.trim = function () {
return this.replace(/^[\s\t ]+|[\s\t ]$/g, '');
}
b. 去掉字符串尾匹配。即改成:
String.prototype.trim = function () {
return this.replace(/^[\s\t ]+/g, '');
}
c.加入多行匹配。即改成:
String.prototype.trim = function () {
return this.replace(/^[\s\t ]+|[\s\t ]+$/mg, '');
}
從以上三種改法結(jié)合文中開頭的NFA資料,我們可以大概的知道trim性能出現(xiàn)問題的原因
量詞限定將優(yōu)先匹配。
量詞限定在結(jié)尾可能會使JS的正則引擎不停的回朔,出現(xiàn)遞歸的一個陷阱,這個遞歸的深度太深。如果字符串更大一點應該會出現(xiàn)棧溢出了。
多行既然能夠匹配,而且性能消耗不大。性能上沒有任何問題,從一個寫這個正則程序的人角度上去看,多行明顯比單行要替換的空串多得多。所以第二點的結(jié)論應該是對的
改良
首先確定匹配字符串的開始正則是沒有任何效率問題的。而匹配結(jié)束的時候會出現(xiàn)性能問題,那可以采用正則與傳統(tǒng)相結(jié)合來改善這個trim性能問題。
例如:
[Ctrl+A 全選 注:引入外部Js需再刷新一下頁面才能執(zhí)行]
如果遇到大數(shù)據(jù)的變長字符串的話就會發(fā)現(xiàn)這個是很耗資源的。效率并不高,有的時候甚至無法忍受。
在解釋這個原因的時候想起以前看到master regular expression里面有提到過。NFA和DFA的引擎是有區(qū)別的。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急于邀功請賞,所以最左子正則式優(yōu)先匹配成功,因此偶爾會錯過最佳匹配結(jié)果;DFA則是“最長的左子正則式優(yōu)先匹配成功”。
4. NFA缺省采用greedy量詞(就是對于/.*/、/\w+/這樣的“重復n”次的模式,以貪婪方式進行,盡可能匹配更多字符,直到不得以罷手為止),NFA會優(yōu)先匹配量詞。
5. NFA可能會陷入遞歸調(diào)用的陷阱而表現(xiàn)得性能極差。
backtracking(回朔)
當NFA發(fā)現(xiàn)自己吃多了,一個一個往回吐,邊吐邊找匹配,這個過程叫做backtracking。由于存在這個過程,在NFA匹配過程中,特別是在編寫不合理的正則式匹配過程中,文本被反復掃描,效率損失是不小的。明白這個道理,對于寫出高效的正則表達式很有幫助。
定位/分析原因
在解釋上面的trim原型方法的時候。經(jīng)過測試,先不說結(jié)果是否正確,有幾個方法是可以化解JS NFA引擎的回朔次數(shù)的
a. 去掉限定的量詞,即改成
復制代碼 代碼如下:
String.prototype.trim = function () {
return this.replace(/^[\s\t ]+|[\s\t ]$/g, '');
}
b. 去掉字符串尾匹配。即改成:
復制代碼 代碼如下:
String.prototype.trim = function () {
return this.replace(/^[\s\t ]+/g, '');
}
c.加入多行匹配。即改成:
復制代碼 代碼如下:
String.prototype.trim = function () {
return this.replace(/^[\s\t ]+|[\s\t ]+$/mg, '');
}
從以上三種改法結(jié)合文中開頭的NFA資料,我們可以大概的知道trim性能出現(xiàn)問題的原因
量詞限定將優(yōu)先匹配。
量詞限定在結(jié)尾可能會使JS的正則引擎不停的回朔,出現(xiàn)遞歸的一個陷阱,這個遞歸的深度太深。如果字符串更大一點應該會出現(xiàn)棧溢出了。
多行既然能夠匹配,而且性能消耗不大。性能上沒有任何問題,從一個寫這個正則程序的人角度上去看,多行明顯比單行要替換的空串多得多。所以第二點的結(jié)論應該是對的
改良
首先確定匹配字符串的開始正則是沒有任何效率問題的。而匹配結(jié)束的時候會出現(xiàn)性能問題,那可以采用正則與傳統(tǒng)相結(jié)合來改善這個trim性能問題。
例如:
您可能感興趣的文章:
- javascript 手機號碼正則表達式驗證函數(shù)
- js正則函數(shù)match、exec、test、search、replace、split使用介紹集合
- js 正則表達式之test函數(shù)講解
- JS驗證URL函數(shù) 正則
- js 替換功能函數(shù),用正則表達式解決,js的全部替換
- js正則表達式之match函數(shù)講解
- JavaScript基于正則表達式的數(shù)字判斷函數(shù)
- 用正則表達式判斷字符串是漢字還是拼音的js函數(shù)代碼
- Js 小數(shù)驗證函數(shù)代碼(基于正則)
- js正則表達式之replace函數(shù)用法
- javascript中基于replace函數(shù)的正則表達式語法
- JavaScript 正則表達式驗證函數(shù)代碼
- JavaScript常用正則函數(shù)用法示例
相關(guān)文章
javascript htmlencode函數(shù)(ff兼容版) 主要是編輯器中反轉(zhuǎn)html代碼
非常不錯的htmlencode 方法,比用正則實現(xiàn)的更好,而且效率高,推薦使用第一種方法。2009-06-06js console.log打印對像與數(shù)組用法詳解
這篇文章主要介紹了js console.log打印對像與數(shù)組用法,結(jié)合實例形式較為詳細的分析了js使用console.log實現(xiàn)打印對象與數(shù)組的具體實現(xiàn)步驟與相關(guān)技巧,需要的朋友可以參考下2016-01-01