Home arrow static arrow Java Programming [Archive] - Data Structure
Warning: Creating default object from empty value in /www/htdocs/w008deb8/wiki/components/com_staticxt/staticxt.php on line 51
Java Programming [Archive] - Data Structure
This topic has 17 replies on 2 pages.    1 | 2 | Next »

Posts:39
Registered: 7/19/04
Data Structure  
Jul 28, 2004 6:29 AM



 
I need to store "500 choose 30" numbers and pass each of those to a function to calculate f(x).
Then I want to sort the numbers say based on ascending order of the result f(x).... what is the best data structure to use. I don't think I will be inserting/deleting items in the middle. The only two operations are calculating f(x) and sorting the based on f(x).

Any help is appreciated.

Thanks.
 

Posts:31,095
Registered: 4/30/99
Re: Data Structure  
Jul 28, 2004 8:11 AM (reply 1 of 17)



 
I have no idea what that is supposed to mean, but if you can use an array, then do so.
 

Posts:10,972
Registered: 10/23/03
Re: Data Structure  
Jul 28, 2004 8:26 AM (reply 2 of 17)



 
Do you mean "500 choose 30" as in 500!/(30! x 370!)...
Do you have any idea how big that is? I estimate it at
27150651130828960494277051851357979774483825553530689528053602409044694613945412266696061862991116719926860945566983943805378822035342127117295781769302476584101773525451082664830821808130237132009168251773264623827210261665539746486154579316933877121872510788729415222872720294281216000000000000000000000000000
 

Posts:5,965
Registered: 5/17/03
Re: Data Structure  
Jul 28, 2004 8:32 AM (reply 3 of 17)



 
Or do you mean 500 times 30 is a 2D array of 15.000 elements?
 

Posts:39
Registered: 7/19/04
Re: Data Structure  
Jul 28, 2004 11:15 AM (reply 4 of 17)



 
Yes, I mean 250 !/(220 ! * 30 !). Yes thats really really huge. I am not sure if using an array list would make sense. I know that a vector would really slow down the run time.
 

Posts:39
Registered: 7/19/04
Re: Data Structure  
Jul 28, 2004 11:16 AM (reply 5 of 17)



 
Yes, it is true. I need to store this many numbers......
 

Posts:10,972
Registered: 10/23/03
Re: Data Structure  
Jul 28, 2004 11:21 AM (reply 6 of 17)



 
Yes, I mean 250 !/(220 ! * 30 !). Yes thats really really huge.

You seem to have scaled down from C(500, 30) to C(250, 30), which is only:
45947961194449778231078045175961362776161865108653562338032320073660403032522643725734437853099511547475279351315541303957507999020641183050835644880383771979233860662343415312192355059626418086750423752925520160469160991633444470533154360130582461856143693413124844285027610436349776361929717655800166634545501656774774684910019321258412150656382273268643238343112492122292355072000000000000000000000000000000000000000000000000
 

Posts:10,972
Registered: 10/23/03
Re: Data Structure  
Jul 28, 2004 11:24 AM (reply 7 of 17)



 
Woops, brain-melt there, C(250, 30) is only 533,650,325,184,459,878,135,989,793,051,885,578,200
 

Posts:39
Registered: 7/19/04
Re: Data Structure  
Jul 28, 2004 11:25 AM (reply 8 of 17)



 
Actually 500 !/ (470 ! * 30 !) will be the worst case while 250 ! / (220 ! * 30 !) could be the best case...
Would I need a hash table..... I don't need to insert/delete in the middle though.
 

Posts:10,972
Registered: 10/23/03
Re: Data Structure  
Jul 28, 2004 11:36 AM (reply 9 of 17)



 
C(250, 30) is only 533,650,325,184,459,878,135,989,793,051,885,578,200.

This is a joke, right? That number (5x10^38) -- your best case -- is intractable.
If each "number" you are working with takes up only 1 byte, that's still 5x10^26 gigabytes.
There isn't that much computer storage on the earth. And that's your best case!
 

Posts:10,972
Registered: 10/23/03
Re: Data Structure  
Jul 28, 2004 11:52 AM (reply 10 of 17)



 
To correct my earlier value, C(500, 30) is 1,445,259,588,120,573,502,872,111,127,079,547,366,704,414,552,400
about 10^48. Here is some code for computing these. (import java.math.*;)
//returns C(n,k) == n!/((n-k)!k!)public static String choose(int n, int k) {    if (n < k)        throw new IllegalArgumentException("n must be >= k");    if (k < 1)        throw new IllegalArgumentException("k must be > 0");     BigInteger kfact = BigInteger.valueOf(1);    for(int i=2; i<=k; ++i)        kfact = kfact.multiply(BigInteger.valueOf(i));     BigInteger prod = BigInteger.valueOf(1);    for(int i=n-k+1; i<=n; ++i)        prod = prod.multiply(BigInteger.valueOf(i));     return prod.divide(kfact).toString();} 
 

Posts:27,518
Registered: 11/3/97
Re: Data Structure  
Jul 28, 2004 12:04 PM (reply 11 of 17)



 
To correct my earlier value, C(500, 30) is
1,445,259,588,120,573,502,872,111,127,079,547,366,704,4
4,552,400 about 10^48.

Probably just me, but I don't think a couple of orders of magnitude either way is going to make a difference.
 

Posts:37,103
Registered: 3/30/99
Re: Data Structure  
Jul 28, 2004 12:09 PM (reply 12 of 17)



 
What's the final k! term in the denominator for again? Is it because we're only considering the elements chosen, and not their order? i.e., chosing 1,2,3,4,5 is equivalent to choosing 3,2,4,5,1?
 

Posts:27,518
Registered: 11/3/97
Re: Data Structure  
Jul 28, 2004 12:10 PM (reply 13 of 17)



 
C(250, 30) is only
533,650,325,184,459,878,135,989,793,051,885,578,200.

This is a joke, right? That number (5x10^38) -- your
best case -- is intractable.
If each "number" you are working with takes up only 1
byte, that's still 5x10^26 gigabytes.
There isn't that much computer storage on the earth.
And that's your best case!


So say the OP wants to cache that in memory, how long would it take the program to start up?

At 10 gigabytes per second, 10^26 gigabytes would take 10^18 years.

The good thing of course is that once the product is delivered to QA the developers won't have to worry about QA finding any bugs (at least not before the Sun becomes a red giant and consumes the earth of course.)
 

Posts:349
Registered: 1/8/04
Re: Data Structure  
Jul 28, 2004 12:11 PM (reply 14 of 17)



 
Probably just me, but I don't think a couple of orders
of magnitude either way is going to make a difference.

I once had the bright idea to make a little program to show every possible 480x640 pixel image by just looping through all (256) colors for each pixel. I deluded myself for a few days with a bad calculation that told me I could do it in few months if I flipped a pixel 60 times a second and reduced the resolution to 240x320. Then I realized I had multiplied where I needed an exponent. The real calculation filled a screen with numbers to show me the number of years it would take. It was amazing.

One of the cool things about really big numbers like that is that when you say "I can do it 1000 times faster by doing X", it really doesn't make a tiny bit of difference.
 
This topic has 17 replies on 2 pages.    1 | 2 | Next »