WEB开发网
开发学院网页设计JavaScript Javascript String 方法效率大比拼 阅读

Javascript String 方法效率大比拼

 2008-12-29 20:04:16 来源:WEB开发网   
核心提示:最初是通过梅子(梅花雪)关于大型字符串拼接效率(1,2)的研究得到启发,Javascript String 方法效率大比拼,最近又看到never-online的从trim原型函数看js正则表达式的性能 ,里面有介绍正则表达式效率陷阱等问题,效率愈低,2. 根据目标字符串,并提出解决方法,我向来对这些鸡毛蒜皮感兴趣

最初是通过梅子(梅花雪)关于大型字符串拼接效率(1,2)的研究得到启发,最近又看到never-online的从trim原型函数看js正则表达式的性能 ,里面有介绍正则表达式效率陷阱等问题,并提出解决方法。我向来对这些鸡毛蒜皮感兴趣,也开始对大型字符串各种方法实现的效率进行比较,并尝试提高这些方法的效率。

1. 大型字符串拼接
如梅子所言,使用数组的join方法确实是最好的实现,可以根据这个思路设计StringBuilder, StringBuffer类。

2. 大型字符串trim
其实never-online在他的文章里有一些说的不准确的地方,代码也不算很精炼。既然这是鸡毛蒜皮的小事,这些零碎东西当然要斤斤计较了。
我很久以前有收集到这样一些实现,I:

String.PRototype.trim = function(){
return this.replace(/(^\s+)(\s+$)/g, '');
};
为了避免正则表达式使用括号带来的消耗,可以写成这样,II:

String.prototype.trim = function(){
return this.replace(/(?:^\s+)(?:\s+$)/g, '');
};
另外有一套实现是这样的,III:

String.prototype.lTrim = function(){
return this.replace(/^\s+/, '');
};
String.prototype.rTrim = function(){
return this.replace(/\s+$/, '');
};
String.prototype.trim = function(){
return this.lTrim().rTrim();
};
其实调用函数也会多少有一点消耗,写成这样或许会快一点点(开个玩笑,这样写会带来一些冗余代码,这时候就需要基于效率(时间)、代码量(空间)和可维护性方面的考量了),IV:

String.prototype.trim = function(){
return this.replace(/^\s+/, '').replace(/\s+$/, '');
};
后来我对正则表达式有了更多的了解,知道了贪婪与非贪婪匹配,于是自作聪明写了这一段:

String.prototype.trim = function(){
return this.replace(/^\s*(.*?)\s*$/, "$1"); // 两端空白字符贪婪匹配,中间字符非贪婪匹配。
};
我曾经为这段代码自鸣得意了好长一段时间,不过后来想到点号不包括换行符,字符串中间有换行符时,返回值就不正确了,于是不情愿的改成这样(多行模式效率也很低),V:

String.prototype.trim = function(){
return this.replace(/^\s*((?:.\n)*?)\s*$/, "$1");
};
谁知,这样的代码遇到大家伙时效率会一落千丈,哎,失败。

原以为String.replace方法比String.substr、String.substring效率低,于是想,只使用正则表达式获得两头(或者一头)的索引位置,然后使用substring方法取出子串,VI:

String.prototype.trim6 = function(){
var l=this.length;
/^[\s]+/.test(this);
var s = RegExp.lastIndex;
s = -1==s?0:s;
// /\s+$/.test(this);
// var e=RegExp.lastIndex;
// var e=this.$lastIndexOf(function(c){return !Char.isBlank(c);})+1;
var e=l;
if(0==l){return '';}
for(var i=l-1,c; i>=0; i--){
c=this.charAt(i);
if(!Char.isBlank(c)){
e=i+1;
break;
}
}
return this.substring(s,e);
};
而最土的方法,莫过于两头都使用循环获得索引了,VII:

String.prototype.trim = function(){
var l=this.length, s=0, e=l;
/*for(var i=0,c; i=0; i--){
c=this.charAt(i);
if(!Char.isBlank(c)){
e=i+1;
break;
}
}*/
return this.substring(s,this.$lastIndexOf(f)+1);
};
代码里老是for啊for的一大串,为了节省字节,而且有可能的话,也准备再优化一下循环,就实现了$indexOf和$lastIndexOf两个方法,可以传递一个返回boolean值的函数作为参数(本来还想也支持正则表达式参数的,想想以前扩展indexOf和lastIndexOf方法后的效率,就算了),这样就可以求得第一个非空白和最后一个非空白字符的位置了。

String.prototype.$indexOf = function(f){
for(var i=0,c,l=this.length; i=0; i--){
c=this.charAt(i);
if(f(c)){return i;}
}
return -1;
};
String.prototype.$lastIndexOf = function(f){
for(var i=this.length-1,c; i>=0; i--){
c=this.charAt(i);
if(f(c)){return i;}
}
return -1;
};

至于说要扩展到支持更长子串和起始索引,以后有需要再说了(顺便说一下,子串越长,有优化算法可以得到更高效率)。
另一个辅助方法:

var Char = {
isBlank:function(c){
//return /\s/.test(c);
return ' '==c '\t'==c '\r\n'==c '\n'==c '\r'==c;
}
};
到了永不在线的算法,VIII:

String.prototype.trim = function(){
var s = this.replace(/^\s+/, '');
var l=s.length, e=l;
if(0==l){return '';}
for(var i=l-1; i>=0; i--){
if(!Char.isBlank(s.charAt(i))){
e=i+1;
break;
}
}
return this.substring(0,e);
};
最初这个算法让我很兴奋,直觉上,感觉这样效率肯定要高,不过事实并不是这么简单。

说到这些实现的效率,无法一概而论,因为不同的字符串,它们的效率比也大不同,甚至异乎寻常。

影响trim方法效率的,主要与字符串的总长度,前面空白字符串长度,后面空白字符串长度,以及前中后的比例有关。详细的效率对比表有时间再上,这里只简要提一下:

对于较小的字符串,各种实现都有不错的表现,而对于大型字符串,则实现I, II表现最为稳定,甚至可以处理超大型字符串。


3. 大型字符串字节长度
即双字节长度为2。注意:这个提法其实也不正确,javascript是使用Unicode字符集的,所有的字符都(有可能)是双字节字符。将汉字等转换为双字节长度主要是为了某些应用。
最土的方法还是循环遍历所有字符,I:

String.prototype.bytes = function(){
var l=this.length, r=l, n=0xff;
for(var i=l; i>=0; i--){
if(this.charCodeAt(i)>n){
r++;
}
}
return r;
};
这里判断字符是否双字节有很多方法,效率较高的之间相差(大概)不大。

另一种实现则看起来很轻灵,寥寥几行,II:

String.prototype.bytes = function(){
return this.replace(/[^\x00-\xff]/g,"xx").length;
};
多动脑子,则想法愈多(也常把简单的事情复杂化),我想如果可以快速取得表达式(双字节/单字节)匹配次数,两值相加应该比较高效,III:

String.prototype.bytes = function(){
return this.length+this.replace(/[\x00-\xff]/g,"").length;
};
IV:

String.prototype.bytes = function(){
return this.length+(this.match(/[^\x00-\xff]/g)"").length;
};
另外看到梅花雪用数组能提供字符串拼接速度,也想:把字符串split为数组,不想对大型字符串而言,这split一步就慢得不行。

bytes方法的效率:使用Javascript脚本循环大型字符串(I),确实远不如内置的replace方法(II)快,而使用正则表达式match方法(IV)又比replace方法(III)稍快,排名第二。

总结:
1. replace方法因匹配而被替换的子串愈长,效率愈低。
2. 根据目标字符串,选择合适的实现。

Tags:Javascript String 方法

编辑录入:爽爽 [复制链接] [打 印]
赞助商链接