Re: Algorithm Question

Lasse Reichstein Nielsen wrote:

Brian Genisio <BrianGenisio (AT) yahoo (DOT) com> writes:

Of course, your algorithm could get real cooky, and be a
binary-recursive algorithm, that will start with "a", and double it,
and double it, and double it, until you get where you need to go. I
think that would be the most efficient way to do it.

Something like:
function aString(n) { // n integer
var ctr = "a";
var acc = "";
while(n>0) {
if (n%2==1) {
acc += ctr;
}
ctr += ctr;
n >>= 1;
}
}

This will take time proportional to n*log(n).

Another approach uses an array to collect the string instead of appending,
and then joint the array at the end. It would be the equivalent of using a
Java StringBuffer. It won't save anything in this case (but that's because
logarithmic exponentiation is very fast). When you are just accumulating
a lot of about equal length strings, it is a good optimization.

function aStringArr(n) {
var arr = [];
while(n>0) {
n--;
arr[n]="a";
}
return arr.join("");
}

/L
--
Lasse Reichstein Nielsen - lrn (AT) hotpop (DOT) com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html
'Faith without judgement merely degrades the spirit divine.'

For the Array solution, I'd personally use:

String.prototype.repeat = function(n) {
var arr = [];
for (var i = 0; i < n; i++) {
arr[i] = this; // or arr.push(this); although it's probably a bit slower

}
return arr.join('');
}

Then you can just do:

var buffer = "a".repeat(5120);

Of course, if the browser supports the Array object and the join() method on the
Array object, just use:

String.prototype.repeat = function(n) {
return (new Array(n + 1)).join(this);
}

var buffer = "a".repeat(5120);
alert(buffer.length + ':' + buffer.substring(0, 20) + '...');

--

Grant Wagner <gwagner (AT) agricoreunited (DOT) com