0
$\begingroup$

I have a doubly link-list like this

typedef struct Record
{
   int i;
   Record* next;
   Record* prev;
}Record;

I have over 5 trillions of records that I need to handle, now that I need to retrieve all of them and sort them out. If its size was small, I could borrow stl's vector or list to do the job but now that it is too huge, I have no idea how to save the object data before sorting is performed

my function prototype

void sortRec(Record**recToSort,bool bASC){}
$\endgroup$

closed as off-topic by D.W., Yuval Filmus, J.-E. Pin, Luke Mathieson, András Salamon Oct 15 '13 at 10:05

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions about software development or programming tools are off-topic here, but can be asked on Stack Overflow." – D.W., Yuval Filmus, J.-E. Pin, Luke Mathieson, András Salamon
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Not sure this is in scope here. $\endgroup$ – Yuval Filmus Oct 2 '13 at 7:01
  • $\begingroup$ Where are the records currently saved? Are they all in memory? In disk? $\endgroup$ – Yuval Filmus Oct 2 '13 at 7:01
  • 1
    $\begingroup$ Use the STXXL if your data doesn't fit into your memory. $\endgroup$ – adrianN Oct 2 '13 at 11:10
2
$\begingroup$

You should also have a look at External Sorting algorithms. This is another book on the subject Algorithms and Data Structures for External Memory

$\endgroup$
1
$\begingroup$

Assuming that the records are really stored in the disk, you can use radix sort. Divide you integer into bytes, and start with the lower-order byte. Open 256 new files, and start going over your database in order, sorting the files according to the lower-order byte. Then do it again with the next byte, this time reading your 256 files in order.

If memory is not at a premium, you could always allocate an array - that will actually be more memory-efficient than a linked list. (Why would you use a linked list for such a big array anyhow? The overhead is 200%.)

$\endgroup$
  • $\begingroup$ Thank you a lot, all records are saved in database and in xml file too $\endgroup$ – Stylin Benjamin Oct 2 '13 at 10:09
1
$\begingroup$

You can merge-sort a list in memory.

Let split(a)->(b,c) be a function that splits the list a so that approximately half the number of elements go into b and the rest goes into c. Time for split should be T(n).

Let merge(a,b)->c be a function that merges the two ordered list a and b into an ordered list c. Time for merge should be T(n).

Sorting can then be performed in O(n*log(n)):

def sort(a):
    if len(a) <= 1:
        return a
    b, c = split(a)
    return merge(sort(b), sort(c))
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.