JavaScript极速狂飙：组合拼接字符串的效率(meizz)

meizz 2005-12-14 03:18:36

在脚本开发过程中，经常会按照某个规则，组合拼接出一个大字符串进行输出。比如写脚本控件时控制整个控件的外观的HTML标签输出，比如AJAX里得到服务器端的回传值后动态分析创建HTML标签时，不过这里我就不讨论拼接字符串的具体应用了，我只是想在这里讨论一下拼接的效率。

字符串的拼接在我们写代码的时候都是用“+=”这个运算符，s += String; 这是我们最为熟知的写法，不知道大家有没有注意过没有，在组合的字符串容量有几十K甚至几百K的时候，脚本执行起来很慢，CPU使用率狂高，例如：

var str = "01234567891123456789212345678931234567894123456789";
str+= "51234567896123456789712345678981234567899123456789\n";
var result = "";
for(var i=0; i<2000; i++) result += str;

就这么一步操作，产生的结果字符串是200K，耗时是1.1秒（这个与电脑配置有关），CPU的峰值100%。（为了更直观地看到效果，我多做了些循环）。可想而知就这么一步操作就消耗了我一秒多的时间，再加上其它的代码的时间消耗，那整个脚本块的执行时间就难以忍受了。那有没有优化的方案呢？还有其它的方法吗？答案当然是有的，否则我写这篇文章就是废话。

更快的方式就是使用数组，在循环拼接的时候不是相接拼接到某个字符串里去，而是把字符串放到一个数组里，最后用数组.join("") 得到结果字符串，代码示例：

var str = "01234567891123456789212345678931234567894123456789";
str+= "51234567896123456789712345678981234567899123456789\n";
var result = "", a = new Array();
for(var i=0; i<2000; i++) a[i] = str;
result = a.join(""); a = null;

大家可以测试测试，组合出一个相同大小的字符串所消耗的时间，我这里测试出来的结果是：<15毫秒，请注意，它的单位是毫秒，也就是说组合出这么一个200K的字符串，两种模式的时间消耗是差不多两个数量级。这意味着什么？意味着后者已经工作结束吃完中饭回来，前者还在做着苦力。我写一个测试页面，大家可以把下面这些代码拷贝下来另存为一个HTM文件在网页里打开自己来测试一下两者之间的效率差，反正我测试的是前者要半分钟才能完成的事，后者0.07秒就搞定了（循环10000次）。

<body>
字符串拼接次数<input id="totle" value="1000" size="5" maxlength="5">
<input type="button" value="字符串拼接法" onclick="method1()">
<input type="button" value="数组赋值join法" onclick="method2()"><br>
<div id="method1"> </div>
<div id="method2"> </div>
<textarea id="show" style="width: 100%; height: 400"></textarea>
<SCRIPT LANGUAGE="JavaScript">

</SCRIPT>

...全文

1205 62 打赏收藏转发到动态举报

写回复

用AI写文章

62 条回复

切换为时间正序

请发表友善的回复…

发表回复

jspadmin 2006-01-03

打赏
举报

使用数组，相比较直接连接，内存开销会不会变大呢？

sjjf 2006-01-02

打赏
举报

可以看出，采用方法一进行拷贝的时候，假设每次拷贝的字符串内容都不同，为str[i](i=1..n)
循环完成了之后，str[1] 被拷贝了n次。str[2]被拷贝了 n-1次....
最终结果出来的字符中，每个字符被操作的次数是一个加权和。
sum = str[1].length*n + str[2].length*(n-1) + ....str[n].length*1
这就是为什么采用方法一在大字符串时会耗时的原因。
我的测试一目的就是检验这个公式的推测。
可惜js借鉴了 java的string而没有照抄 stringBuffer.

测试二的目的是想确定对象在创建时的时间，此外也想验证一下js引擎在何时进行gc，
因为最初我推想慢的原因是因为gc频繁触发。

(网友木野狐给我过一篇关于js引擎的片断介绍。偶保存下来了，忘了那个网址。
资料较少，偶也迷迷糊糊的，也有一大堆疑问。不能作为解释这个帖子的证据。)

Every now and then the garbage collector runs. First it puts a "mark" on every object, variable, string, etc – all the memory tracked by the GC. (JScript uses the VARIANT data structure internally and there are plenty of extra unused bits in that structure, so we just set one of them.)

Second, it clears the mark on the scavengers and the transitive closure of scavenger references. So if a scavenger object references a nonscavenger object then we clear the bits on the nonscavenger, and on everything that it refers to. (I am using the word "closure" in a different sense than in my earlier post.)

后来发现，结果数据显示似乎与js引擎解析变量引用，和gc的关系不大。
(要么有些因素一起存在于方法一和方法二，要么方法一和方法二不存在那些因素，
这里的因素指代不明的影响内容,要不就是我对js引擎的认识有误，最后一个理由成立的概率很大)

//方法二
function method2()
{
var result = "";
var totle = parseInt(document.getElementById("totle").value);
var n = new Date().getTime();

var a = new Array();
var tt = new String("tt");
for(var i=0; i<totle; i++)
{
// 如果没有达到gc激活的条件，这里应该会有很多对象的，但是不知道怎么验证。
tt = new String(str+"--"+i);
a[i] = tt;
}
result = a.join(""); a=null;

var s = "数组赋值join法：拼接后的大字符串长 "+ result.length +"字节，"+
"拼接耗时 "+ (new Date().getTime()-n) +"毫秒！";
document.getElementById("method2").innerHTML = s;
document.getElementById("show").value = result;
}

sjjf 2006-01-02

打赏
举报

试着对这个现象作了一下解析。
测试一：

//var str = "01234567891123456789212345678931234567894123456789";
// str+= "51234567896123456789712345678981234567899123456789\n";
var str = "0";

在运行一下数据。结果自己运行来看。

测试二：恢复测试一中的var str数据
//方法一
function method1()
{
var result = "";
var totle = parseInt(document.getElementById("totle").value);
var n = new Date().getTime();

for(var i=0; i<totle; i++)
{
//result += str; //将这一行改成下一行。
result = null; //
result = new String(str+"--"+i);
}

var s = "字符串拼接法：拼接后的大字符串长 "+ result.length +"字节，"+
"拼接耗时 "+ (new Date().getTime()-n) +"毫秒！";
document.getElementById("method1").innerHTML = s;
document.getElementById("show").value = result;
}

得到的结果如下：
字符串拼接法：拼接后的大字符串长 101字节，拼接耗时 47毫秒！(这个是改过的)
数组赋值join法：拼接后的大字符串长 10099899字节，拼接耗时 422毫秒！(这个是没有改过的)

======================================================
个人推测如下：

1. js的 string应该和java的string 类差不多，
java对类string 这样描述：类string 的实例代表unicode字符的序列。
一个string对象具有一个不变得值，字符串文字是对类string的实例的引用。

str = "aa";
str += "bb";
str开始时指向字符串常量"aa"
当执行str += "bb";时是依据"aa","bb"创建一个"aabb"
然后把指向"aa"的引用指向"aabb"
这时候系统共存在三个字符串常量"aa","bb","aabb"
至于"aa","bb", 他们会在他们的作用域里存在，

参照js的帮助手册：concat()方法
说明
concat 方法的结果等于：result = string1 + string2 + string3 + … + stringN。
不论源字符串或结果字符串哪一个中的值改变了都不会影响另一个字符串中的值。
如果有不是字符串的参数，在被连接到 string1 之前将先被转换为字符串。

偶觉得 str += "bb"; 的实现方法应该和 concat差不多吧？
也许实现上,操作符重载部分的代码更高效些吧。

采用
for(var i=0; i<totle; i++)
{
result += str;
}

意味着它的实现必然会开辟一段空间将原字符串和新的字符串拷贝到新的空间。
参考java的concat()的方法： (src/java/lang/string.java)
/**
* Concatenates the specified string to the end of this string.
* 略....
*/
public String concat(String str) {
int otherLen = str.length();
if (otherLen == 0) {
return this;
}
char buf[] = new char[count + otherLen];
getChars(0, count, buf, 0);
str.getChars(0, otherLen, buf, count);
return new String(0, count + otherLen, buf);
}

/**
* Copies characters from this string into the destination character
* array.
* 略....
*/
public void getChars(int srcBegin, int srcEnd, char dst[], int dstBegin) {
if (srcBegin < 0) {
throw new StringIndexOutOfBoundsException(srcBegin);
}
if (srcEnd > count) {
throw new StringIndexOutOfBoundsException(srcEnd);
}
if (srcBegin > srcEnd) {
throw new StringIndexOutOfBoundsException(srcEnd - srcBegin);
}
System.arraycopy(value, offset + srcBegin, dst, dstBegin,
srcEnd - srcBegin);
}
(我没有找到java操作符重载部分的内容，也不想去解析字节码了，解析那个东西还需要找指令来对照，麻烦！)