Yesterday, I posted an entry about a clever way to implement string multiplication in JavaScript using Array.prototype.join()
In comments, redraiment challenged me, suggesting that an implementation based on string doubling would be more efficient. Sure, I thought, for really large values of n, but surely for small n, using the native join() method would be better, wouldn't it?
It turns out that writing a good algorithm is better than being overly clever (at least in these days of really good JIT interpreters). Here's my new string multiplication code:
String.prototype.times = function(n) {
var s = this, total = "";
while(n > 0) {
if (n % 2 == 1) total += s;
if (n == 1) break;
s += s;
n = n>>1;
}
return total;
};
By my simple benchmarks, this implementation is significantly faster than using join(), even when only multiplying by 1 or 2. I've tested it in Firefox 3.5, IE 8 and Safari 3.
Just add array join to save some memory and in theory, it is faster.
String.prototype.times = function(n) {
var s = this, total = [];
while(n > 0) {
if (n % 2 == 1) total[total.length] = s;
if (n == 1) break;
s += s;
n = n>>1;
}
return total.join('');
};
use bit operation ant binary in mind, to do it as follows, i think the break line is kind of waste loop, only take effect at last step ...
String.prototype.times = function(n) {
var s = this, total = [];
while(n) {
if (n & 1) total[total.length] = s;
s += s;
n = n>>1;
}
return total.join('');
};
In the latest browsers, with their highly-optimized js interpreters, I've found that string concatenation with + is faster than the join() trick. It may still be worth doing in IE, however. In this case, the loop is not likely to have more than 10 iterations, however, and I suspect that the join() optimization doesn't help much, and in some cases it might slow it down.
Similarly, I'd be surprised if replacing %2 with &1 actually makes any difference at all. This seems like the kind of thing that a good JS interpreter will already optimize for you.
Too much cleverness like this makes your code hard to read, and it may well not make the code any faster!
Hi David,
You are right, thank you for your reply. Actually I learn JavaScript from your "The definitive Guide - 4th Edition", which is the best JS book I ever read so far.
I have tested that in the new browser your method is always faster, and the break out of loop thing is useful especially when the duplicate parameter are large.
I still need to learn to make the code more readable, maintainable.
Tried to make something readable, efficient while use reasonable memory, can be further optimized, just another way...
String.prototype.times = function(n) {
var s = this, c = n;
do {
s += s;
} while (n = n>>1)
s = s.substring(0, this.length * c);
return s;
};