Thread: How to deal with memory...

  1. #1
    Registered User
    Join Date
    Apr 2006
    Posts
    25

    How to deal with memory...

    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.

  2. #2
    Registered User
    Join Date
    Mar 2006
    Posts
    725
    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.
    Code:
    #include <stdio.h>
    
    void J(char*a){int f,i=0,c='1';for(;a[i]!='0';++i)if(i==81){
    puts(a);return;}for(;c<='9';++c){for(f=0;f<9;++f)if(a[i-i%27+i%9
    /3*3+f/3*9+f%3]==c||a[i%9+f*9]==c||a[i-i%9+f]==c)goto e;a[i]=c;J(a);a[i]
    ='0';e:;}}int main(int c,char**v){int t=0;if(c>1){for(;v[1][
    t];++t);if(t==81){J(v[1]);return 0;}}puts("sudoku [0-9]{81}");return 1;}

  3. #3
    Registered User
    Join Date
    Apr 2006
    Posts
    25
    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 ?
    Last edited by trongsi; 06-02-2006 at 12:05 PM.

  4. #4
    Registered User
    Join Date
    Apr 2006
    Posts
    25
    Nobody helps me out . Is something wrong with my question ?

  5. #5
    Registered User
    Join Date
    Aug 2005
    Location
    Austria
    Posts
    1,990
    Quote Originally Posted by trongsi
    Nobody helps me out . Is something wrong with my question ?
    Nothing wrong with the question but jafet has given the solution for your question.
    google "merge sort"
    Kurt

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > 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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  7. #7
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    > 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:
    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.
    Look on the bright side--when you do this, you are getting closer to a sorted file.
    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.

  8. #8
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    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.
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  9. #9
    Registered User
    Join Date
    Apr 2006
    Posts
    25
    Thanks all for your help.
    To Salem,
    Quote Originally Posted by Salem
    > 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.
    <---- 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.
    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.

  10. #10
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > 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)
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  11. #11
    Registered User
    Join Date
    Apr 2006
    Posts
    25
    Quote Originally Posted by Salem
    > 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.
    Thank you all.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Relate memory allocation in struct->variable
    By Niara in forum C Programming
    Replies: 4
    Last Post: 03-23-2007, 03:06 PM
  2. Managing shared memory lookups
    By clancyPC in forum Linux Programming
    Replies: 0
    Last Post: 10-08-2003, 04:44 AM
  3. Accessing Video Memory Information...need help
    By KneeLess in forum C++ Programming
    Replies: 8
    Last Post: 08-24-2003, 03:53 PM
  4. Is it necessary to write a specific memory manager ?
    By Morglum in forum Game Programming
    Replies: 18
    Last Post: 07-01-2002, 01:41 PM
  5. What's the best memory (RAM) type?
    By Unregistered in forum A Brief History of Cprogramming.com
    Replies: 17
    Last Post: 12-15-2001, 12:37 AM