Algorithm Question

Discussion in 'Javascript' started by Home Newbie, Apr 1, 2004.

  1. Home Newbie

    Home Newbie Guest

    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";
    }
    Home Newbie, Apr 1, 2004
    #1
    1. Advertising

  2. 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
    Brian Genisio, Apr 1, 2004
    #2
    1. Advertising

  3. Brian Genisio <> 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 -
    DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
    'Faith without judgement merely degrades the spirit divine.'
    Lasse Reichstein Nielsen, Apr 1, 2004
    #3
  4. Home Newbie

    Evertjan. Guest

    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)
    Evertjan., Apr 1, 2004
    #4
  5. Home Newbie

    Grant Wagner Guest

    Lasse Reichstein Nielsen wrote:

    > Brian Genisio <> 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 -
    > 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 = 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 <>
    Grant Wagner, Apr 2, 2004
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. ortoped

    Search algorithm question

    ortoped, Aug 19, 2003, in forum: Java
    Replies:
    1
    Views:
    387
    Miguel De Anda
    Aug 19, 2003
  2. Ahmed Moustafa
    Replies:
    0
    Views:
    766
    Ahmed Moustafa
    Nov 15, 2003
  3. Anna Smith

    Graph Algorithm Question

    Anna Smith, Apr 24, 2004, in forum: Java
    Replies:
    2
    Views:
    873
    Mladen Adamovic
    Apr 24, 2004
  4. BlueBall
    Replies:
    12
    Views:
    631
    Dale King
    Apr 15, 2006
  5. Bapaiah Katepalli
    Replies:
    1
    Views:
    1,483
    Mike Treseler
    Jun 23, 2006
Loading...

Share This Page