home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / sources / d / 1220 < prev    next >
Encoding:
Internet Message Format  |  1992-09-04  |  2.3 KB
  1. Xref: sparky comp.sources.d:1220 alt.sources.d:1061
  2. Newsgroups: comp.sources.d,alt.sources.d
  3. Path: sparky!uunet!dcatlas!joet
  4. From: joet@dcatlas.dot.gov (Joe Trott)
  5. Subject: Re: Sorting in Virtual Memory
  6. Message-ID: <1992Aug27.201457.26498@dcatlas.dot.gov>
  7. Organization: U.S Dept. of Transportation
  8. References: <1992Aug27.093506.11349@sniap.mchp.sni.de>
  9. Date: Thu, 27 Aug 1992 20:14:57 GMT
  10. Lines: 40
  11.  
  12. frank@D012S436.sniap.mchp.sni.de () writes:
  13.  
  14. >I'm writing a program which needs to sort a large array 
  15. >parts of which are swapped in and out of memory (my own
  16. >implementation of a sort of VM).
  17.  
  18. >The array is divided up into pages of size ~8K which are
  19. >swapped to disk as necessary on a LRU basis.  
  20.  
  21. >Does anyone know of a sorting algorithm which will work in 
  22. >harmony with this LRU paging?  I can quicksort the elements 
  23. >of each individual page of the array, but then the problem 
  24. >is to sort the pages themselves with the minimum amount 
  25. >of swapping.  Traditional sort alrgorithms optimise on
  26. >comparisons - what I want is also to optimise the *order*
  27. >of comparison, I think.  Any ideas?
  28.  
  29. Would it be feasible to consider each page somewhat like a "stack", and 
  30. "pop" the lowest one off whichever stack holds it?  I.e. sort each page 
  31. (stack) and then compare the "top card" from each stack.  If it is the
  32. lowest (highest if a descending sort), write it to output and pop that
  33. stack.  It doesn't matter which stack gets emptied first, or how quickly,
  34. since you will always be "popping" the lowest (| highest) value off of
  35. whichever stack has it.  Think of it like piles of playing cards, face up.
  36. Each pile is already sorted.  You just take the lowest (| highest) card
  37. showing and put it directly in your output pile.  When done, the output pile
  38. will be sorted (though in reverse order).  In your algorithm, you only need
  39. to read the page for the stack you just popped; the "top cards" from all
  40. other stacks simply remain in memory for comparison.  You reread the popped
  41. stack for the next value, and then rewrite it minus the value you popped.
  42. Of course, if the same stack has the next lower value as well, you needn't
  43. reread it, as it is the one still in memory.  You can make this faster if
  44. you write each stack as a random-access file once it is sorted.  This way, you
  45. only need to read single values from any given stack, and merely update its
  46. file pointer.
  47.  
  48. Hope this helps. 
  49.  
  50. -JTT
  51.  
  52.