Sun 18 Nov 2007
Today saw a post from Steve on his blog about ” Fast String Multiplication with Regular Expressions, Exponential Concatenation, and Binary Interpolation“. Basically, it deals with how to fast multiplicate a string n times in javascript.
When I first saw the post, only 3 algorithms were presented. Looking at the 3rd algorithm, I think it can receive some improvement if exponential concatenation is used more efficiently. By the time I implement the improved version, Steve added a 4th one to his post, which is quite similar to what I have here:
function mul5(str, n) {
var r=[];
while(n){
if(n%2)
r.push(str);
str+=str;
n >>=1;
}
return r.join('');
}
The main difference is that it is more compact. My tests show that, in Firefox and Safari 3.0.4, mul5 is as fast as mul4. However, similar to mul4, mul5 is about 30% slower than mul3 in IE (mult5 performs as good as mul4 in IE).
The reason of slowdown in IE compared to mul3 is this part: str+=str. IE does not handle that direct string concatenation well if the string is quite long. What if we use array.push there as well? After several fail-and-error, I found out one solution which will actually boost the performance for IE:
function mul5(str, n) {
var r=[],t=[str];
while(n){
if(n%2)
r.push.apply(r,t);
t.push.apply(t,t);
n >>=1;
}
return r.join('');
}
As shown above, the trick is to use array.push.apply(array,anotherArray) to add all elements in anotherArray to array. This IE version is as good as mul3, or even slightly faster than it.
However, this modification will slow down other browsers. We can use conditional compilation support in IE to work around this. The merged version is like this:
function mul5(str, n) {
var r=[];
/*@cc_on //for IE
var t=[str];
while(n){
if(n%2)
r.push.apply(r,t);
t.push.apply(t,t);
n >>=1;
}
return r.join('');
@*/
while(n){
if(n%2)
r.push(str);
str+=str;
n >>=1;
}
return r.join('');
}
If using dojo, the conditional compilation should be changed to just test dojo.isIE. (conditional compilation is not supported by dojo builder, so it will be lost when building dojo)
Try it yourself here. Changes compared to the original one:
- mul1 and mul2 are slow, so removed from the test
- the number of repetition and the length of the input str are slightly different from the original one
- A table is used to present the result, rather than a list
