🚀 go-pugleaf

frank@D012S436.sniap.mchp.sni.de () writes:

>I'm writing a program which needs to sort a large array 
>parts of which are swapped in and out of memory (my own
>implementation of a sort of VM).

>The array is divided up into pages of size ~8K which are
>swapped to disk as necessary on a LRU basis.  

>Does anyone know of a sorting algorithm which will work in 
>harmony with this LRU paging?  I can quicksort the elements 
>of each individual page of the array, but then the problem 
>is to sort the pages themselves with the minimum amount 
>of swapping.  Traditional sort alrgorithms optimise on
>comparisons - what I want is also to optimise the *order*
>of comparison, I think.  Any ideas?

Would it be feasible to consider each page somewhat like a "stack", and 
"pop" the lowest one off whichever stack holds it?  I.e. sort each page 
(stack) and then compare the "top card" from each stack.  If it is the
lowest (highest if a descending sort), write it to output and pop that
stack.  It doesn't matter which stack gets emptied first, or how quickly,
since you will always be "popping" the lowest (| highest) value off of
whichever stack has it.  Think of it like piles of playing cards, face up.
Each pile is already sorted.  You just take the lowest (| highest) card
showing and put it directly in your output pile.  When done, the output pile
will be sorted (though in reverse order).  In your algorithm, you only need
to read the page for the stack you just popped; the "top cards" from all
other stacks simply remain in memory for comparison.  You reread the popped
stack for the next value, and then rewrite it minus the value you popped.
Of course, if the same stack has the next lower value as well, you needn't
reread it, as it is the one still in memory.  You can make this faster if
you write each stack as a random-access file once it is sorted.  This way, you
only need to read single values from any given stack, and merely update its
file pointer.

Hope this helps. 

-JTT

frank@D012S436.sniap.mchp.sni.de () writes:
: I'm writing a program which needs to sort a large array 
: parts of which are swapped in and out of memory (my own
: implementation of a sort of VM).
: 
[ Request for algorithm deleted ].

Check out Knuth Vol ? (Sorting and Searching).  Turn to the section on
external sorts.  This was very common in the days when core referred to
ferrite donuts threaded on wires.  Lots of algorithms.

-- Binayak

/ hpfcso:comp.sources.d / frank@D012S436.sniap.mchp.sni.de () /  3:35 am  Aug 27, 1992 /
I'm writing a program which needs to sort a large array 
parts of which are swapped in and out of memory (my own
implementation of a sort of VM).

The array is divided up into pages of size ~8K which are
swapped to disk as necessary on a LRU basis.  

Does anyone know of a sorting algorithm which will work in 
harmony with this LRU paging?  I can quicksort the elements 
of each individual page of the array, but then the problem 
is to sort the pages themselves with the minimum amount 
of swapping.  Traditional sort alrgorithms optimise on
comparisons - what I want is also to optimise the *order*
of comparison, I think.  Any ideas?


Any help appreciated,
Frank O'Dwyer
--
Frank O'Dwyer		       			Disclaimer: 
Siemens-Nixdorf AG 	                        I will deny everything
Tel.  : +49 (89) 636-40639                      Fax.  : +49 (89) 636-45860
e-mail: Frank.ODwyer@sniap.mchp.sni.de
----------

/ hpfcso:comp.sources.d / ericw@hpfcso.FC.HP.COM (Eric Widhalm) / 11:14 am  Sep  1, 1992 /
/ hpfcso:comp.sources.d / frank@D012S436.sniap.mchp.sni.de () /  3:35 am  Aug 27, 1992 /
I'm writing a program which needs to sort a large array 
parts of which are swapped in and out of memory (my own
implementation of a sort of VM).

The array is divided up into pages of size ~8K which are
swapped to disk as necessary on a LRU basis.  

Does anyone know of a sorting algorithm which will work in 
harmony with this LRU paging?  I can quicksort the elements 
of each individual page of the array, but then the problem 
is to sort the pages themselves with the minimum amount 
of swapping.  Traditional sort alrgorithms optimise on
comparisons - what I want is also to optimise the *order*
of comparison, I think.  Any ideas?


Any help appreciated,
Frank O'Dwyer
--
Frank O'Dwyer		       			Disclaimer: 
Siemens-Nixdorf AG 	                        I will deny everything
Tel.  : +49 (89) 636-40639                      Fax.  : +49 (89) 636-45860
e-mail: Frank.ODwyer@sniap.mchp.sni.de
----------
----------

In article <7290002@hpfcso.FC.HP.COM> ericw@hpfcso.FC.HP.COM (Eric Widhalm) writes:
>/ hpfcso:comp.sources.d / frank@D012S436.sniap.mchp.sni.de () /  3:35 am  Aug 27, 1992 /
>I'm writing a program which needs to sort a large array 
>parts of which are swapped in and out of memory (my own
>...
>of swapping.  Traditional sort alrgorithms optimise on
>comparisons - what I want is also to optimise the *order*
>of comparison, I think.  Any ideas?

Quicksort isn't as bad as you think.  In one pass of Quicksort, the algorithm
scans the array *sequentially* from both ends, occasionally swapping elements.
Thus, in one pass of Quicksort, each page of the array is swapped in once.
Furthermore, once the component elements get smaller than 8K, quicksort needs
no swaps at all.  Thus, the swapping complexity of quicksort should be the
same as its comparison complexity, n**2 in the worst case, but n*log(n)
on the average.

If you really want to sort first and them merge, try one of the merge 
algorithms that we used to use for tape-based sorting (see Knuth for details).
Since rewinding a tape was *slow*, these algorithms tried to minimize the 
passes through the tapes, which might translate into minimizing the accesses
to the pages.
-- 
Joseph A. Reuter, Wizard-in-Training
Speaking for myself from reuter@venice.sedd.trw.com
"Olorin I was in the West that is forgotten." -- J.R.R. Tolkien
"You can't win, you can't break even, and you can't quit the game."

frank@D012S436.sniap.mchp.sni.de () writes:

> I'm writing a program which needs to sort a large array 
> parts of which are swapped in and out of memory (my own
> implementation of a sort of VM).

[E-mail to the asker bounced.]

I have no proof, but after thinking about it, it seems to me that MERGESORT
  would give you the best performance, ASSUMING that you can't get away with
  a BUCKETSORT or a RADIXSORT (look those up if you don't know -- they are
  order n, not the usual n-log-n).

The reason for this is that MERGESORT, for much of it's execution, is very
  localized.  In fact, I would not be surprised if this were the optimum
  sorting for your problem...

If you get a true answer, please post a summary!