Algorithm Question

[Home Newbie]

I have some stupid questions....

- Why would program 1 run a lot faster than program 2? Can someone explain?
If I change the sample_size to be a larger one, program 2 will my
browser freeze!!
- What is the optimum value (1024 in this case) to use?

Program 1:
-----------
int sample_size = 5120; // 5K
for (i=0; i < (sample_size/1024); i++) {
my_buffer = "";
for (j=1; j<=1024; j++) {
my_buffer += "a";
}
my_data += my_buffer;
}

Program 2:

 

[Brian Genisio]

I have some stupid questions....

- Why would program 1 run a lot faster than program 2? Can someone explain?
If I change the sample_size to be a larger one, program 2 will my
browser freeze!!
- What is the optimum value (1024 in this case) to use?

Program 1:
-----------
int sample_size = 5120; // 5K
for (i=0; i < (sample_size/1024); i++) {
my_buffer = "";
for (j=1; j<=1024; j++) {
my_buffer += "a";
}
my_data += my_buffer;
}

Program 2:
------------
int sample_size = 5120; // 5K
for (i=0; i < sample_size; i++) {
my_data += "a";
}

Yeah, I understand why this is... Kind of quirky, but it the way strings
work in Javascript... similar to the way Java handles strings.

In Javascript, a string is immutable. This means that the data within a
string cannot be changed by an operator. So, an operator such as +=
does not append the data to the string. Instead, it makes a copy of the
string, appends the data, and assigns it to itself.

So, (my_data += "a") really is (my_data = my_data + "a").

In memory, conceptually, it is more like this:

tmp_var = my_data;
my_data = tmp_var + 1;

So, in Program 1, there is no itteration where you copy more than 1024
characters in (my_buffer += "a"), and you only ever copy more than 1024
bytes 4 times in (my_data += my_buffer).

In Program 2, once you reach 1028, you begin to be slower than Program
2, since every step you are copying 1029, 1030, 1031, etc characters per
execution. As you can see, it is a heck of a lot more than 5 times
slower.

A quicker algorithm would be to do something like:

my_buffer = "";
my_data = "";

for (j=0; j<=1024; j++)
my_buffer += "a";

for (j=0; j<=5; i++)
my_data += my_buffer;

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.

I hope this all makes sense.

Brian

 

[Lasse Reichstein Nielsen]

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

 

[Evertjan.]

Lasse Reichstein Nielsen wrote on 01 apr 2004 in comp.lang.javascript:

Another approach uses an array to collect the string instead of
appending, and then joint the array at the end.

I thought about that, Lasse, but in the end
a cannabis joint will slow you down.

 

[Grant Wagner]

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

For the Array solution, I'd personally use:

String.prototype.repeat = function(n) {
var arr = [];
for (var i = 0; i < n; i++) {
arr = 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) + '...');