Printable View
Hi every body,
Suppose that someone created a linked list with say some thousands nodes, and he saved those list as a file.
Assume that my computer is poor of resource, and its memory can not handle such a data. So if I wanted to open that file, read the rest of that list to memory in case to sort its items, how could I do that ?
I vaguely heard of memory paging, but I don't know how to do.
Can everybody please explain what it is and how it works ?
Thanks in advance.
Well, first you'll need to be able to read each list node from the file one by one.
If you really don't have the RAM to handle only a few thousand nodes, you could use temporary disk files to store unsorted values, while only sorting several elements in memory at a time.
Of course, it would be rather slow, since disk access is slow.
Mergesort may be used for such an operation. You could store unmerged lists in temporary files in a folder, and merged lists in files in another. Merge back and forth until you get a single file in one of the folders -- sorted.
The point is that when we read a part of the file, say 1000 / 5000 nodes, and sort that part, and so we repeat that step for 4 other parts. The result we have will be 5 sorted segments of one file, but the whole file is not totally sorted. Consider the following example:
Assume I have a list of 10 items: m,c,a,s,z,p,q,d,l,n.
I read one half of the list and sort it: a,c,m,s,z.
Then I read another half and sort it: d,l,n,p,q.
The result is : a,c,m,s,z,d,l,n,p,q. <--- is not the expected result that we wanted the whole list sorted like this: a,c,d,l,m,n,p,q,s,z.
I'm just curious of how people handle this kind of thing by writing their own code, instead of using some predefined functions of others. Because predefined functions were written by people, too, so how did they do in process ?
**************************
Edit:
I'm waiting so long for your help :( , everybody can help me go through this question ?
Nobody helps me out :( . Is something wrong with my question ?
Nothing wrong with the question but jafet has given the solution for your question.Quote:
Originally Posted by trongsi
google "merge sort"
Kurt
> I read one half of the list and sort it: a,c,m,s,z.
> Then I read another half and sort it: d,l,n,p,q.
Then you do a merge, which basically goes
- read a from file 1
- read d from file 2
- compare (a is before d)
- output a, and replace with c from file 1
- compare (c is before d)
- output c and replace with m from file 1
t's a merge - you read each successive element from both files, and output whichever is the smaller, and replace with the next element from the respective input file.
> The point is that when we read a part of the file, say 1000 / 5000 nodes, and sort that part, and so we repeat that step for 4 other parts.
The problem is that if you expect to have the whole file sorted correctly in one go, you would have to read the whole file in and sort it. The fastest any sort algorithm can run is O(n) because the sort algorithm needs to look at all the elements at least once to sort them correctly. By splitting up the file and sorting that, you are setting it up for failure.
It is not to say that the solution you employ is bad:Look on the bright side--when you do this, you are getting closer to a sorted file.Quote:
Assume I have a list of 10 items: m,c,a,s,z,p,q,d,l,n.
I read one half of the list and sort it: a,c,m,s,z.
Then I read another half and sort it: d,l,n,p,q.
The result is : a,c,m,s,z,d,l,n,p,q. <--- is not the expected result that we wanted the whole list sorted like this: a,c,d,l,m,n,p,q,s,z.
Basically, you will have to keep running the algorithm in a loop until the list is fully sorted and there is nothing to swap in place, or whatever algorithm you used. If it goes through the file and nothing needs to be sorted set a bool variable and break the loop.
You can see how merge sort (and other sorts) works here . All you need to do is copy/paste the code into your own header file.
Thanks all for your help.
To Salem,
<---- and the result will be 1 file merged by 2 files above, or 2 files re-rorted ? If it's 1 file, so we will encounter the memory overflow as the problem I addressed before because the final file will contain the whole list that exceeds the memory. That's why I tried to break up into files.Quote:
Originally Posted by Salem
Ex: Assume I break the whole very long long list into say 10 files and sort them, like you suggested. After that, I start to merge file 1 and 2, what is the result ? 1 file combined by the 2s, or 2 separate files ?
- If 1, then I start to merge it with file 3, produces a bigger file.
- Merge that file with 4, produces a bigger one, and so forth until my memory can not handdle the file that is bigger in size than its available capacity.
> and the result will be 1 file merged by 2 files above, or 2 files re-rorted ?
You end up with a single file, which is the sorted result of both input files.
> Assume I break the whole very long long list into say 10 files and sort them,
You can merge from 10 files just as easily from 2 files. The algorithm is the same
- read a record from each file
- find the smallest record
- write it to the output file
- replace it with the next record from the appropriate input file
> Merge that file with 4, produces a bigger one, and so forth until
The whole point of merging is that the whole file is NOT stored in memory in one go.
Only one record from each file is in memory at any point in time.
Take a pack of cards
- shuffle them
- split into two approximately equal stacks
- sort each stack by whatever rule you want
- now merge sort both stacks, the limited memory are your two hands
= pick the top card from each stack and put the sorted one on the new (output stack)
Thank Salem, I'll go through this vague concept by studying more.Quote:
Originally Posted by Salem
Thank you all.