In Search for a better Algorithm

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

  1. Guest

    Hi,

    I was working on the following problem and I managed to get a
    solution, but it's too slow. And I am still in search for a better
    algorithm. Please enlighten me.

    --------------------------------------------------------------------------------------------
    Here's my solution
    #include <stdio.h>

    int array[200][200][200] = {0};

    int main(){
    int n;
    char c;
    if(scanf("%d\n", &n) != 1)
    return 1;
    while(1){
    int sum = 0;
    int x = 0, y = 0, z = 0, x2 = 0, y2 = 0, z2 =0, i, j, k,
    num=0;
    if(scanf("%c", &c) == EOF)
    break;
    switch(c){
    case 'A':
    if(scanf("%d %d %d %d\n", &x, &y, &z, &num) !=
    4)
    return 1;
    array[x-1][y-1][z-1] += num;
    break;
    case 'S':
    if(scanf("%d %d %d %d\n", &x, &y, &z, &num) !=
    4)
    return 1;
    array[x-1][y-1][z-1] -= num;
    break;
    case 'Q':
    if(scanf("%d %d %d %d %d %d\n", &x, &y, &z,
    &x2, &y2, &z2) != 6)
    return 1;

    for(i = x; i < x2+1; i++){
    for(j = y; j < y2+1; j++){
    for(k = z; k < z2+1; k++){
    sum+=array[i-1][j-1][k-1];
    }
    }
    }
    printf("%d\n", sum);
    break;
    default:
    goto end;
    break;
    }
    }
    end:
    return 0;
    }

    --------------------------------------------------------------------------------------------
    This is the question

    Prince Ray wants to marry his girl friend, beautiful Princess Amy. Amy
    loves Ray, and is very willing to take him. However, Amy's father,
    King StreamSpeed, insists that his son in law should be talented
    enough, so that he could let him be the King of this country after
    King StreamSpeed retired. So he gives Ray a Test.
    Ray is given a large brick of size n*n*n, which contains n*n*n grids
    of size 1. Every grid can be represent as a triple(x, y, z) (1<=x, y,
    z<=n). There are numbers in every grid. All the numbers are initially
    set to zero.
    King StreamSpeed will do three operations to the brick.
    1. Add a number to a given grid's number
    2. Subtract a number from a given grid's number
    3. Query the sum of total number from(x1,y1,z1) to (x2,y2,z2)
    (x1 <= x2, y1 <= y2, z1 <= z2)
    As Ray 's best friend and most excellent coder, you are required to
    write a program to answer all the queries to help Ray marry with her
    valentine.

    ÊäÈë

    The first line of the input contains an integer n(1<=n<=100), the size
    of the brick. Then follow several lines in the following format:
    A x y z num : Add num to (x, y, z)
    S x y z num: Subtract num from (x, y, z)
    Q x1 y1 z1 x2 y2 z2 : Query the sum of numbers from (x1, y1 , z1) to
    (x2 , y2 , z2)
    The number of all the queries will be no more than 1000000.Input file
    is ended by a zero and should not be processed.



    Êä³ö

    For every query in the input file, your program should output the
    corresponding result -- the sum of numbers in the range (x1, y1, z1)
    ~(x2, y2, z2). The result does not exceed 10^9.

    ÑùÀýÊäÈë

    10
    A 1 1 4 5
    A 2 5 4 5
    Q 1 1 1 10 10 10
    S 3 4 5 34
    Q 1 1 1 10 10 10
    0

    ÑùÀýÊä³ö

    10
    -24

    Ìáʾ

    Huge input file, scanf is recommended.
     
    , Sep 28, 2007
    #1
    1. Advertising

  2. CBFalconer Guest

    "" wrote:
    >
    > I was working on the following problem and I managed to get a
    > solution, but it's too slow. And I am still in search for a
    > better algorithm. Please enlighten me.
    >
    > ----------------------------------------------------------------
    > Here's my solution
    > #include <stdio.h>
    >
    > int array[200][200][200] = {0};


    That array has 8,000,000 elements, and even if they are just 1 char
    elements you will have a tough time finding a machine with enough
    memory to implement it. That means it will always have to be in
    virtual memory, and involve disk transfers.

    You can probably get away with an array of 40,000 pointers to 200
    unit arrays. There you can avoid the storage entirely by
    representing empty arrays with a NULL pointer.

    Please do not exceed 72 char line length. 67 is better.

    --
    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 28, 2007
    #2
    1. Advertising

  3. On Thu, 27 Sep 2007 20:58:48 -0700, ""
    <> wrote:

    >Hi,
    >

    [snip statement and code]

    You have posted this before in comp.lang.c. This is the wrong
    newsgroup - try comp.programming. You received useful
    information in the responses to your original post that you seem
    to have ignored. Try posting to an appropriate newsgroup; when
    you do read the responses to your post.


    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 28, 2007
    #3
  4. Guest

    On 9ÔÂ28ÈÕ, ÏÂÎç12ʱ51·Ö, (Richard Harter) wrote:
    > On Thu, 27 Sep 2007 20:58:48 -0700, ""
    >
    > <> wrote:
    > >Hi,

    >
    > [snip statement and code]
    >
    > You have posted this before in comp.lang.c. This is the wrong
    > newsgroup - try comp.programming. You received useful
    > information in the responses to your original post that you seem
    > to have ignored. Try posting to an appropriate newsgroup; when
    > you do read the responses to your post.
    >
    > Richard Harter, ://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


    thanks
     
    , Sep 28, 2007
    #4
  5. jacob navia Guest

    CBFalconer wrote:
    > "" wrote:
    >> I was working on the following problem and I managed to get a
    >> solution, but it's too slow. And I am still in search for a
    >> better algorithm. Please enlighten me.
    >>
    >> ----------------------------------------------------------------
    >> Here's my solution
    >> #include <stdio.h>
    >>
    >> int array[200][200][200] = {0};

    >
    > That array has 8,000,000 elements, and even if they are just 1 char
    > elements you will have a tough time finding a machine with enough
    > memory to implement it. That means it will always have to be in
    > virtual memory, and involve disk transfers.
    >



    Please Chuck...

    I have 2GB RAM installed, and at work I have routinely
    4GB machines!

    An array of 8MB is quite small this days. Yes, I know this
    is inflation, but it is the way everything goes.

    But maybe you are still using your famous 486?
    In that case, 8MB is a lot of course.


    > You can probably get away with an array of 40,000 pointers to 200
    > unit arrays. There you can avoid the storage entirely by
    > representing empty arrays with a NULL pointer.
    >
    > Please do not exceed 72 char line length. 67 is better.
    >


    Same thing. Screens of 1900x1200 pixels are common this days,
    and I can't even buy a screen with less than 1280x1024. Why
    72 chars line length?

    Your post gives the impression to the (possible) younger
    people that we are a hopelessly backward bunch of old guys
    living somewhere in the 80s.

    jacob
     
    jacob navia, Sep 28, 2007
    #5
  6. Ian Collins Guest

    jacob navia wrote:
    >
    > Same thing. Screens of 1900x1200 pixels are common this days,
    > and I can't even buy a screen with less than 1280x1024. Why
    > 72 chars line length?
    >

    Now come on Jacob, you've been here long enough to know that the
    regulars here still read Usenet on their Teletypes or Wise terminals
    over a 110 baud, 19" modem.

    --
    Ian Collins.
     
    Ian Collins, Sep 28, 2007
    #6
  7. Chris Torek Guest

    [OT drift, probably should not post this at all, but it is late :) ]

    In article <>
    Ian Collins <> wrote:
    >... you've been here long enough to know that the
    >regulars here still read Usenet on their Teletypes or Wise terminals
    >over a 110 baud, 19" modem.


    That's "Wyse", not "Wise". I prefer my H19 though. Wyse magic
    cookies, ugh. :)

    (Actually, my H19 died years ago. Built it in the mid-1980s ...
    a few years later, the decode chip for the keyboard got squirrelly,
    but I found that a pullup resistor on one of the pins would make
    it reliable. Kept the thing going until the mid-1990s or so.
    Also, the first modem I personally owned was a Telebit Trailblazer.
    I did have to use 110 baud for a while, though, as the 300 baud
    mode on the acoustic coupler built in to the Silent 700 I had
    borrowed suffered from too much noise.)

    (Also, there was at least one Wyse that did not suffer so badly
    from the "magic cookie" problem. I forget which model, but
    Pyramid liked to use it as their console display. The U of MD
    had one of the early wire-wrapped Pyramid machines.)
    --
    In-Real-Life: Chris Torek, Wind River Systems
    Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
    email: forget about it http://web.torek.net/torek/index.html
    Reading email is like searching for food in the garbage, thanks to spammers.
     
    Chris Torek, Sep 28, 2007
    #7
  8. [comp.lang.c] CBFalconer <> wrote:

    > "" wrote:


    >> int array[200][200][200] = {0};


    > That array has 8,000,000 elements, and even if they are just 1 char
    > elements you will have a tough time finding a machine with enough
    > memory to implement it.


    As Jacob noted, that's sizeof(int)*8,000,000 bytes; we all have
    machines that can handle that if they're so inclined. Whether there
    is that much automatic storage available is another question (as we
    all know). Perhaps that's what you meant to refer to.

    > You can probably get away with an array of 40,000 pointers to 200
    > unit arrays. There you can avoid the storage entirely by
    > representing empty arrays with a NULL pointer.


    An array of 200 int**'s would eliminate the "probably", but I did not
    see the original post, so I couldn't say whether that would be
    helpful.

    > Please do not exceed 72 char line length. 67 is better.


    67 sounds a little overzealous to me; the line length here is 70.

    --
    C. Benson Manica | I appreciate all corrections, polite or otherwise.
    cbmanica(at)gmail.com |
    ----------------------| I do not currently read any posts posted through
    sdf.lonestar.org | Google groups, due to rampant unchecked spam.
     
    Christopher Benson-Manica, Sep 28, 2007
    #8
  9. Richard Guest

    Christopher Benson-Manica <> writes:

    > [comp.lang.c] CBFalconer <> wrote:
    >
    >> "" wrote:

    >
    >>> int array[200][200][200] = {0};

    >
    >> That array has 8,000,000 elements, and even if they are just 1 char
    >> elements you will have a tough time finding a machine with enough
    >> memory to implement it.

    >
    > As Jacob noted, that's sizeof(int)*8,000,000 bytes; we all have
    > machines that can handle that if they're so inclined. Whether there
    > is that much automatic storage available is another question (as we
    > all know). Perhaps that's what you meant to refer to.
    >
    >> You can probably get away with an array of 40,000 pointers to 200
    >> unit arrays. There you can avoid the storage entirely by
    >> representing empty arrays with a NULL pointer.

    >
    > An array of 200 int**'s would eliminate the "probably", but I did not
    > see the original post, so I couldn't say whether that would be
    > helpful.
    >
    >> Please do not exceed 72 char line length. 67 is better.

    >
    > 67 sounds a little overzealous to me; the line length here is 70.


    Please pay no attention to Falconer. Until he learns to post with one
    signature that is.
     
    Richard, Sep 28, 2007
    #9
  10. osmium Guest

    <> wrote:

    I was working on the following problem and I managed to get a
    solution, but it's too slow. And I am still in search for a better
    algorithm. Please enlighten me.

    --------------------------------------------------------------------------------------------
    Here's my solution
    #include <stdio.h>

    int array[200][200][200] = {0};

    Look up sparse arrays on the Web. I really detest the way your instructor
    worded that problem. Maybe it is a cultural thing ....

    <snip>
     
    osmium, Sep 28, 2007
    #10
  11. "CBFalconer" <> a écrit dans le message de news:
    ...
    > "" wrote:
    >>
    >> int array[200][200][200] = {0};

    >
    > That array has 8,000,000 elements, and even if they are just 1 char
    > elements you will have a tough time finding a machine with enough
    > memory to implement it. That means it will always have to be in
    > virtual memory, and involve disk transfers.


    Unless the OP is programming on very old hardware, a 32MB array should not
    be concern.
    Furthermore, the OP knows the value of n is in the range 1 <= n <= 100. Why
    not test that in the program and reduce the array to ``int
    array[100][100][100]'' ?

    It might also be more efficient to use powers of 2 for the array dimensions,
    such as ``int array[128][128][128]'' but the potential gains on address
    calculations may be lost to cache collisions.

    Test these propositions, ans see if it helps speed up the program.

    > You can probably get away with an array of 40,000 pointers to 200
    > unit arrays. There you can avoid the storage entirely by
    > representing empty arrays with a NULL pointer.


    I'm afraid that would lead to an even slower program, defeating the OPs
    goal.

    > Please do not exceed 72 char line length. 67 is better.


    For posting on Usenet, short lines are better indeed, but I would not limit
    program lines to 67 in actual program sources.

    --
    Chqrlie.
     
    Charlie Gordon, Sep 29, 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. Ahmed Moustafa
    Replies:
    0
    Views:
    781
    Ahmed Moustafa
    Nov 15, 2003
  2. Bapaiah Katepalli
    Replies:
    1
    Views:
    1,498
    Mike Treseler
    Jun 23, 2006
  3. Replies:
    39
    Views:
    1,649
    Charlie Gordon
    Nov 12, 2007
  4. Abby Lee
    Replies:
    5
    Views:
    421
    Abby Lee
    Aug 2, 2004
  5. Replies:
    5
    Views:
    206
    Randy Kobes
    Oct 12, 2005
Loading...

Share This Page