JScriptのメソッドの速度/join(3)

Arrayには長さ1の文字列が2n個格納されているとする。
これを順に結合していくとする。
結合にかかる時間は、結合された結果の文字列の長さに比例し、
長さが1なら単位時間かかるとする。
すべての結合にかかる時間は、

2 + ... + 2n = 2n-1(2n + 1) - 1

となる。
別の方法を考える。
まず長さ2の文字列をざっと作って、次に長さ4の文字列を作って、
という方法。

"a" + "b" + "c" + "d" = "ab" + "cd" = "abcd"

という具合。
これだと、かかる時間は、

n2n

というわけで、2n-1 と nの比較になり、
圧倒的に後者のほうが速いということになる。


これをコードで表現しようとすると、
ややメモリがいるがこう書ける。


Array.prototype.join3 = function(s) {
if(s == undefined)
s = ",";

var length = this.length;
if(length == 0)
return "";

// まず隣同士を結合して新しいArrayを作る
var a = [ ];
var i;
for(i = 0; i < length >> 1; i++)
a[i] = this[i*2] + s + this[i*2+1];
if(length & 1)
a[i] = this[length-1];

// 隣同士を結合してArrayに上書き
// Arrayの長さが1になったら終わり
while((length = a.length) > 1) {
length = a.length;
for(i = 0; i < length >> 1; i++)
a[i] = a[i*2] + s + a[i*2+1];
if(length & 1)
a[i++] = a[length-1];
a.length = i;
}

return a[0];
}

長さ100の文字列を1000個つなげるのに、
join : 160ms、自作 : 19024msに対して、
今回の自作 : 905msとなった。
ずいぶん速くなったが、それでもjoinよりかなり遅い。
やっぱりjoinを使ったほうがよい。