Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Javascript > Algorithm Question

Reply
Thread Tools

Algorithm Question

 
 
Home Newbie
Guest
Posts: n/a
 
      04-01-2004
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";
}




 
Reply With Quote
 
 
 
 
Brian Genisio
Guest
Posts: n/a
 
      04-01-2004
Home Newbie wrote:

> 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








 
Reply With Quote
 
 
 
 
Lasse Reichstein Nielsen
Guest
Posts: n/a
 
      04-01-2004
Brian Genisio <(E-Mail Removed)> 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 - http://www.velocityreviews.com/forums/(E-Mail Removed)
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'
 
Reply With Quote
 
Evertjan.
Guest
Posts: n/a
 
      04-01-2004
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.

--
Evertjan.
The Netherlands.
(Please change the x'es to dots in my emailaddress)
 
Reply With Quote
 
Grant Wagner
Guest
Posts: n/a
 
      04-02-2004
Lasse Reichstein Nielsen wrote:

> Brian Genisio <(E-Mail Removed)> 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 - (E-Mail Removed)
> 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 <(E-Mail Removed)>

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Filtered Back Projection Algorithm (FBP Algorithm) Bapaiah Katepalli VHDL 1 06-23-2006 04:50 PM
ForLoop Performance / Algorithm question BlueBall Java 12 04-15-2006 03:45 AM
Graph Algorithm Question Anna Smith Java 2 04-24-2004 04:55 PM
Key generation algorithm and Cipher algorithm Ahmed Moustafa Java 0 11-15-2003 06:35 AM
Search algorithm question ortoped Java 1 08-19-2003 09:53 PM



Advertisments