468,550 Members | 2,480 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,550 developers. It's quick & easy.

In Search for a better Algorithm

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 '07 #1
10 1253
On Thu, 27 Sep 2007 20:58:48 -0700, "we********@gmail.com"
<we********@gmail.comwrote:
>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, cr*@tiac.net
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
Sep 28 '07 #2
"we********@gmail.com" 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

Sep 28 '07 #3
On 9月28日, 下午12时51分, c...@tiac.net (Richard Harter) wrote:
On Thu, 27 Sep 2007 20:58:48 -0700, "weidong...@gmail.com"

<weidong...@gmail.comwrote:
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, c...@tiac.nethttp://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 '07 #4
CBFalconer wrote:
"we********@gmail.com" 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
Sep 28 '07 #5
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.
Sep 28 '07 #6
[OT drift, probably should not post this at all, but it is late :-) ]

In article <5m************@mid.individual.net>
Ian Collins <ia******@hotmail.comwrote:
>... 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 (4039.22'N, 11150.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.
Sep 28 '07 #7
[comp.lang.c] CBFalconer <cb********@yahoo.comwrote:
"we********@gmail.com" 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.
Sep 28 '07 #8
Christopher Benson-Manica <at***@otaku.freeshell.orgwrites:
[comp.lang.c] CBFalconer <cb********@yahoo.comwrote:
>"we********@gmail.com" 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.
Sep 28 '07 #9
<we********@gmail.comwrote:

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>
Sep 28 '07 #10
"CBFalconer" <cb********@yahoo.coma 閏rit dans le message de news:
46***************@yahoo.com...
"we********@gmail.com" 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.
Sep 29 '07 #11

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

10 posts views Thread by pembed2003 | last post: by
4 posts views Thread by Axel | last post: by
28 posts views Thread by joshc | last post: by
8 posts views Thread by Ben Fidge | last post: by
12 posts views Thread by Divick | last post: by
33 posts views Thread by Bertram Trabant | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.