@ above can u plz specify how to sort a 1 Tb file with 64 bytes of Ram. I got this heap method....but ur approach seems interesting ......if u can give some links dat wud be very appreciated..
On Thu, Jun 24, 2010 at 1:01 AM, Douglas Diniz <[email protected]> wrote: > If you have a memory that has less than 1 million integers, you have > to sort through co-sequential process (File Structures in C++, Folk), > that use heapsort too, and list the first 1 million integers from the > sorted file. > With this method you can have only 64bytes of Ram (or less, depending > of your file register size) to sort a 1Tb file. > > On Wed, Jun 23, 2010 at 4:06 PM, Dave <[email protected]> wrote: > > Form the first million numbers into a max-heap, where the largest > > number at the root. Any number in the input file that is larger than > > the root can be ignored. If it is smaller than the root, replace the > > root with the number and trickle it down the heap to restore the heap > > condition. Worst case is if the file is in descending order, in which > > case, there are about 2 * 0.999999 trillion * log_2(1 million) data > > comparisons. > > > > Dave > > > > On Jun 23, 7:18 am, amit <[email protected]> wrote: > >> Given a set of 1 Trillion integers on hard disk, find the smallest 1 > >> million of them. You can fit at most 1 million integers in memory at a > >> time. State the fastest solution you can think of. > > > > -- > > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > > To post to this group, send email to [email protected]. > > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > > > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
