Optimization Problem

Discussion in 'C Programming' started by weidongtom@gmail.com, Sep 25, 2007.

  1. Guest

    Hi,

    I was submitting a solution of a certain problem to the online judge,
    but it says my program is exceeding the time limit, I've been doing
    some tweaks to my codes but still it didn't get me through, so please
    help me out here. Thanks in advance.

    /* Input:
    A x y z num {to add num to array[x][y][z]}
    or
    S x y z num {to sub num from array[x][y][z]
    or
    Q x1 y1 z1 x2 y2 z2 {where x1<= xi <= x2, y1<= yi <= y2, z1<= zi <=
    z2, find the sums of all the values xi, yi, zi}
    */

    #include <stdio.h>
    #include <stdlib.h>

    int array[300*300*300]={0};

    int main(){
    int n, x1, y1, z1, x2, y2, z2, num, total = 0, n_square;
    char action;
    scanf("%d\n", &n);
    n_square= n*n;

    while(1){
    int sum = 0;
    if(scanf("%c", &action) == EOF)
    return 1;
    switch(action){
    case '0':
    return 0;
    case 'A':
    scanf("%d %d %d %d\n", &x1, &y1, &z1, &num);
    array[(x1-1)+(y1-1)*n+(z1-1)*n_square] += num;
    total += num;
    break;
    case 'S':
    scanf("%d %d %d %d\n", &x1, &y1, &z1, &num);
    array[(x1-1)+(y1-1)*n+(z1-1)*n_square] -= num;
    total -= num;
    break;
    case 'Q':
    scanf("%d %d %d %d %d %d\n", &x1, &y1, &z1,
    &x2, &y2, &z2);
    if(x1 == 0 && x2 == n && y1 == 0 && y2 == n &&
    z1 == 0 && z2 == n)
    printf("%d\n", total);
    else{
    int i, j , k;
    for(i = x1; i < x2+1; i++){
    for(j = y1; j < y2+1; j++){
    for(k = z1; k < z2+1; k++){
    sum += array[(i-1)+(j-1)*n+
    (k-1)*n_square];
    }
    }
    }
    printf("%d\n", sum);
    }
    break;
    default:
    return 1;
    }
    }
    return 0;
    }
    , Sep 25, 2007
    #1
    1. Advertising

  2. user923005 Guest

    To find out where the time is going with your program, use a profiler.
    The GNU gprof profiler is free.
    user923005, Sep 25, 2007
    #2
    1. Advertising

  3. user923005 said:

    > To find out where the time is going with your program, use a profiler.
    > The GNU gprof profiler is free.


    Context is always useful.

    --
    Richard Heathfield <http://www.cpax.org.uk>
    Email: -http://www. +rjh@
    Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
    "Usenet is a strange place" - dmr 29 July 1999
    Richard Heathfield, Sep 25, 2007
    #3
  4. Willem Guest

    wrote:
    ) I was submitting a solution of a certain problem to the online judge,
    ) but it says my program is exceeding the time limit, I've been doing
    ) some tweaks to my codes but still it didn't get me through, so please
    ) help me out here. Thanks in advance.

    You can't know what will increase the speed of your program without
    testing, but there's something about your code that tends to be very
    sub-optimal on most modern computers:

    ) <snip>
    ) int i, j , k;
    ) for(i = x1; i < x2+1; i++){
    ) for(j = y1; j < y2+1; j++){
    ) for(k = z1; k < z2+1; k++){
    ) sum += array[(i-1)+(j-1)*n+
    ) (k-1)*n_square];
    ) }
    ) }
    ) }
    ) printf("%d\n", sum);
    ) <snip>

    The memory on most modern PCs is such that when you read it in order,
    it goes a lot faster. So when you access a lot of elements of an array,
    try to do it so that you read element X+1 after reading element X.


    SaSW, Willem
    --
    Disclaimer: I am in no way responsible for any of the statements
    made in the above text. For all I know I might be
    drugged or something..
    No I'm not paranoid. You all think I'm paranoid, don't you !
    #EOT
    Willem, Sep 25, 2007
    #4
  5. "" <> writes:

    > I was submitting a solution of a certain problem to the online judge,
    > but it says my program is exceeding the time limit, I've been doing
    > some tweaks to my codes but still it didn't get me through, so please
    > help me out here. Thanks in advance.


    > scanf("%d\n", &n);


    > if(scanf("%c", &action) == EOF)


    > scanf("%d %d %d %d\n", &x1, &y1, &z1, &num);


    > scanf("%d %d %d %d\n", &x1, &y1, &z1, &num);


    > scanf("%d %d %d %d %d %d\n", &x1, &y1, &z1,
    > &x2, &y2, &z2);


    You should (almost) always test the result for scanf. When you do
    test the result, it is almost always better to test for success (== 1,
    == 4, etc) rather than for one type of failure (== EOF).

    --
    Ben.
    Ben Bacarisse, Sep 25, 2007
    #5
  6. user923005 Guest

    On Sep 25, 11:55 am, Richard Heathfield <> wrote:
    > user923005 said:
    >
    > > To find out where the time is going with your program, use a profiler.
    > > The GNU gprof profiler is free.

    >
    > Context is always useful.


    The title together with the statements is all that is needed in this
    follow-up.
    Nothing additional will be gained by stating (for instance) the
    particulars about the problem.
    IMO-YMMV.
    user923005, Sep 26, 2007
    #6
  7. CBFalconer Guest

    user923005 wrote:
    > Richard Heathfield <> wrote:
    >> user923005 said:
    >>
    >>> To find out where the time is going with your program, use a
    >>> profiler. The GNU gprof profiler is free.

    >>
    >> Context is always useful.

    >
    > The title together with the statements is all that is needed in
    > this follow-up. Nothing additional will be gained by stating
    > (for instance) the particulars about the problem. IMO-YMMV.


    You don't realize the situation, especially using the google
    interface to Usenet. Usenet is a best efforts delivery
    philosophy. There is no guarantee that any other reader of your
    post has ever, or ever will, be able to read any other posts in the
    thread. This makes it essential to quote sufficient material in
    each reply so that that reply stands by itself.

    Even the google interface is capable of doing this, judging by
    other posters.

    --
    Chuck F (cbfalconer at maineline dot net)
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net>



    --
    Posted via a free Usenet account from http://www.teranews.com
    CBFalconer, Sep 26, 2007
    #7
  8. CBFalconer said:

    > user923005 wrote:
    >> Richard Heathfield <> wrote:
    >>> user923005 said:
    >>>
    >>>> To find out where the time is going with your program, use a
    >>>> profiler. The GNU gprof profiler is free.
    >>>
    >>> Context is always useful.

    >>
    >> The title together with the statements is all that is needed in
    >> this follow-up. Nothing additional will be gained by stating
    >> (for instance) the particulars about the problem. IMO-YMMV.

    >
    > You don't realize the situation, especially using the google
    > interface to Usenet.


    I doubt that very much; user923005 has been around the block a few times,
    and he knows exactly how Usenet works. He's just being ornery. The only
    cure for his intransigence is the edge of Dann Corbit's poleaxe.

    <snip>

    --
    Richard Heathfield <http://www.cpax.org.uk>
    Email: -http://www. +rjh@
    Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
    "Usenet is a strange place" - dmr 29 July 1999
    Richard Heathfield, Sep 26, 2007
    #8
  9. On Tue, 25 Sep 2007 05:38:45 -0700, ""
    <> wrote:

    >Hi,
    >
    >I was submitting a solution of a certain problem to the online judge,
    >but it says my program is exceeding the time limit, I've been doing
    >some tweaks to my codes but still it didn't get me through, so please
    >help me out here. Thanks in advance.
    >
    >/* Input:
    >A x y z num {to add num to array[x][y][z]}
    >or
    >S x y z num {to sub num from array[x][y][z]
    >or
    >Q x1 y1 z1 x2 y2 z2 {where x1<= xi <= x2, y1<= yi <= y2, z1<= zi <=
    >z2, find the sums of all the values xi, yi, zi}
    >*/
    >
    >#include <stdio.h>
    >#include <stdlib.h>


    Do you use anything declared in stdlib.h?

    >
    >int array[300*300*300]={0};


    If the requirement is to deal with up to 300 elements in each
    dimension, make the array 301*301*301.

    By using a 1D array to simulate a 3D array, you eliminate any help the
    compiler can give you in terms of optimizing array access. You do not
    gain a single byte of space.

    >
    >int main(){
    > int n, x1, y1, z1, x2, y2, z2, num, total = 0, n_square;
    > char action;
    > scanf("%d\n", &n);


    You should test that n is between 1 and whatever the maximum dimension
    is.

    > n_square= n*n;
    >
    > while(1){
    > int sum = 0;
    > if(scanf("%c", &action) == EOF)
    > return 1;


    This is a non-portable return value from main. Furthermore, you
    should not be exiting the program at this point. You should only be
    exiting the while loop.

    > switch(action){
    > case '0':
    > return 0;


    This is a portable return value but still not the time to be exiting
    main.

    > case 'A':
    > scanf("%d %d %d %d\n", &x1, &y1, &z1, &num);


    You should check the return value from scanf to insure you received
    all four values.

    I assume the online judge is redirecting stdin to a file. scanf is a
    pretty complex function. I wonder if it would be faster to use fgets
    followed by a series of calls to strtol.

    > array[(x1-1)+(y1-1)*n+(z1-1)*n_square] += num;


    Eliminate the -1 terms in all the expressions. You might want to make
    the array element expression a macro to save typing.

    > total += num;


    While you are debugging your code, add something like

    printf("Case A: x=%d, y=%d, z=%d, num=%d, array=%d,
    total=%d\n", x1, y1, z1, num, array[...], total);

    > break;
    > case 'S':
    > scanf("%d %d %d %d\n", &x1, &y1, &z1, &num);
    > array[(x1-1)+(y1-1)*n+(z1-1)*n_square] -= num;
    > total -= num;


    Same two comments apply.

    > break;
    > case 'Q':
    > scanf("%d %d %d %d %d %d\n", &x1, &y1, &z1,
    > &x2, &y2, &z2);


    Check to make sure scanf found all six inputs.

    > if(x1 == 0 && x2 == n && y1 == 0 && y2 == n &&
    >z1 == 0 && z2 == n)


    0 should never be a valid input. All six inputs should be range
    checked.

    > printf("%d\n", total);
    > else{


    A good place for some more debugging output.

    > int i, j , k;
    > for(i = x1; i < x2+1; i++){
    > for(j = y1; j < y2+1; j++){
    > for(k = z1; k < z2+1; k++){
    > sum += array[(i-1)+(j-1)*n+
    >(k-1)*n_square];
    > }
    > }
    > }
    > printf("%d\n", sum);
    > }


    Here also.

    > break;
    > default:
    > return 1;


    Do you really want to quit the program here? Do you even want to quit
    the while loop because of an unexpected input?

    > }
    > }
    > return 0;


    Your only way out of the while loop is via the return statements. This
    statement can never execute. The return statements in the while
    should be break statements so you get here. Before returning from
    main, you should print some end of job message.

    >}



    Remove del for email
    Barry Schwarz, Sep 26, 2007
    #9
  10. CBFalconer Guest

    "" wrote:
    >
    > I was submitting a solution of a certain problem to the online
    > judge, but it says my program is exceeding the time limit, I've
    > been doing some tweaks to my codes but still it didn't get me
    > through, so please help me out here. Thanks in advance.


    Maybe the time limit is on when to submit entries?

    --
    Chuck F (cbfalconer at maineline dot net)
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net>



    --
    Posted via a free Usenet account from http://www.teranews.com
    CBFalconer, Sep 26, 2007
    #10
  11. On Tue, 25 Sep 2007 05:38:45 -0700, ""
    <> wrote:

    >Hi,
    >
    >I was submitting a solution of a certain problem to the online judge,
    >but it says my program is exceeding the time limit, I've been doing
    >some tweaks to my codes but still it didn't get me through, so please
    >help me out here. Thanks in advance.
    >


    [snip code]

    You have had several execellent responses commenting on your C
    code; learn from them. However your problem is not a C problem;
    it is a programming problem.
    <OT>
    The essence of the problem is that you have a large sparse array
    in which almost all entries are zero. You alter entries in an
    interactive loop. Upon demand you print out the sum of all
    entries within a subarray.

    The programming issue is that the cost of looping through the
    entire array is enormous whereas the cost of looping through the
    actual number of non-zero entries is small, that being no more
    than the number of interactive entries.

    The point of the problem is to devise a choose a data structure
    and algorithm for which the cost is proportional to the actual
    size of the non-zero data.

    Repost in comp.programming if you want suggestions about doing
    that.
    </OT>

    Richard Harter,
    http://home.tiac.net/~cri, http://www.varinoma.com
    But the rhetoric of holistic harmony can generate into a kind of
    dotty, Prince Charles-style mysticism. -- Richard Dawkins
    Richard Harter, Sep 26, 2007
    #11
    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. JE
    Replies:
    0
    Views:
    449
  2. ashu
    Replies:
    5
    Views:
    1,184
    umerarain
    May 16, 2006
  3. JE
    Replies:
    2
    Views:
    392
    Karl Heinz Buchegger
    Aug 5, 2004
  4. DENG
    Replies:
    6
    Views:
    293
  5. Ravikiran

    Zero Optimization and Sign Optimization???

    Ravikiran, Nov 17, 2008, in forum: C Programming
    Replies:
    22
    Views:
    839
    Thad Smith
    Nov 24, 2008
Loading...

Share This Page