 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, brainmelt 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!/((nk)!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=nk+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.  
