Re: [math-fun] Optimally sorting a cyclic group
Yes, a radix-style sort will work; I had forgotten about that. I'm working on a model where every access is expensive, and RAM access is not even remotely constant time. In this particular problem, I can *preprocess for free* to determine the complete permutation, but then I have to pay full retail price for actually applying this permutation to rearrange the data records. I was hoping to minimize rearrangements in the cases where the data was already "almost sorted". I was thinking along the lines of Quicksort, which is pretty good when the data is already almost sorted. At 10:05 AM 4/20/2018, Tomas Rokicki wrote:
A linear walk can notice and preserve the cyclic walk else abort. For what disorder distribution do you want to do better?
If you have such a field as you describe radix sort is linear time, as discussed in TAOCP.
On Fri, Apr 20, 2018 at 12:56 PM Henry Baker <hbaker1@pipeline.com> wrote:
Suppose you have N records in which one of the fields is a number 0..(N-1), and there is exactly one record for each number 0..(N-1).
It is trivial to sort such a set using traditional Knuth-TAOCP algorithms.
However, if I don't care that the first record is labelled "0", but only care that the final ordering preserves the *cyclic* ordering of the group, can I do any better?
Obviously, I can't do a lot better, since cyclicly rotating the ordering costs O(N), while sorting costs O(NlogN), but is there a clever way to sort w/o putting "0" at the front and "(N-1)" at the end? In particular, is there a way to sort that automatically notices when the records are already in cyclic order, and doesn't bother making any further changes. -- http://cube20.org/ -- http://golly.sf.net/ --
If preprocessing is truly free, then at worst you need only simulate each of the N different scenarios without actually moving the associated data and see which one would be cheapest. (ie run through the cases, for k=0..N-1, simulating sorting the permutation using the predicates Pk := i < j just when (i-k)\N < (j-k)\N) Perhaps for a specific sorting algorithm you can compute the merit for each Pk more directly, without actually undertaking the simulation, thus being cheaper than free.
On Apr 20, 2018, at 11:14 AM, Henry Baker <hbaker1@pipeline.com> wrote:
Yes, a radix-style sort will work; I had forgotten about that.
I'm working on a model where every access is expensive, and RAM access is not even remotely constant time.
In this particular problem, I can *preprocess for free* to determine the complete permutation, but then I have to pay full retail price for actually applying this permutation to rearrange the data records.
I was hoping to minimize rearrangements in the cases where the data was already "almost sorted".
I was thinking along the lines of Quicksort, which is pretty good when the data is already almost sorted.
At 10:05 AM 4/20/2018, Tomas Rokicki wrote:
A linear walk can notice and preserve the cyclic walk else abort. For what disorder distribution do you want to do better?
If you have such a field as you describe radix sort is linear time, as discussed in TAOCP.
On Fri, Apr 20, 2018 at 12:56 PM Henry Baker <hbaker1@pipeline.com> wrote:
Suppose you have N records in which one of the fields is a number 0..(N-1), and there is exactly one record for each number 0..(N-1).
It is trivial to sort such a set using traditional Knuth-TAOCP algorithms.
However, if I don't care that the first record is labelled "0", but only care that the final ordering preserves the *cyclic* ordering of the group, can I do any better?
Obviously, I can't do a lot better, since cyclicly rotating the ordering costs O(N), while sorting costs O(NlogN), but is there a clever way to sort w/o putting "0" at the front and "(N-1)" at the end? In particular, is there a way to sort that automatically notices when the records are already in cyclic order, and doesn't bother making any further changes. -- http://cube20.org/ -- http://golly.sf.net/ --
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
What is the cost for a swap vs copying to and from another location? On Fri, Apr 20, 2018 at 2:45 PM Marc LeBrun <mlb@well.com> wrote:
If preprocessing is truly free, then at worst you need only simulate each of the N different scenarios without actually moving the associated data and see which one would be cheapest. (ie run through the cases, for k=0..N-1, simulating sorting the permutation using the predicates Pk := i < j just when (i-k)\N < (j-k)\N)
Perhaps for a specific sorting algorithm you can compute the merit for each Pk more directly, without actually undertaking the simulation, thus being cheaper than free.
On Apr 20, 2018, at 11:14 AM, Henry Baker <hbaker1@pipeline.com> wrote:
Yes, a radix-style sort will work; I had forgotten about that.
I'm working on a model where every access is expensive, and RAM access is not even remotely constant time.
In this particular problem, I can *preprocess for free* to determine the complete permutation, but then I have to pay full retail price for actually applying this permutation to rearrange the data records.
I was hoping to minimize rearrangements in the cases where the data was already "almost sorted".
I was thinking along the lines of Quicksort, which is pretty good when the data is already almost sorted.
At 10:05 AM 4/20/2018, Tomas Rokicki wrote:
A linear walk can notice and preserve the cyclic walk else abort. For what disorder distribution do you want to do better?
If you have such a field as you describe radix sort is linear time, as discussed in TAOCP.
On Fri, Apr 20, 2018 at 12:56 PM Henry Baker <hbaker1@pipeline.com> wrote:
Suppose you have N records in which one of the fields is a number 0..(N-1), and there is exactly one record for each number 0..(N-1).
It is trivial to sort such a set using traditional Knuth-TAOCP algorithms.
However, if I don't care that the first record is labelled "0", but only care that the final ordering preserves the *cyclic* ordering of the group, can I do any better?
Obviously, I can't do a lot better, since cyclicly rotating the ordering costs O(N), while sorting costs O(NlogN), but is there a clever way to sort w/o putting "0" at the front and "(N-1)" at the end? In particular, is there a way to sort that automatically notices when the records are already in cyclic order, and doesn't bother making any further changes. -- http://cube20.org/ -- http://golly.sf.net/ --
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
similar but with a twist: say I generated the set of bracelets (necklaces with reversal) of 0 or 1 with n beads, with no more than floor(n/2) beads equal to 1. Define the polynomial 'p' of the bracelet as Sum(k=index of 1 in the bracelet position; z^k). Then, can I define a 'leader' bracelet such that appending any number m of extra 0-beads to it (resulting in a bracelet with n+m beads) has the same 'leader bracelet' polynomial p? In other words, can there exist an ordering of such (0-1) strings where the least element is is unchanged by appending zero's?
Yes, we could (in theory) simulate every possible permutation, which might be worth it -- e.g., suppose we have N=10,000 cars to arrange in a cyclic order, but we eventually have to physically move them into position; moving them into position might not be straightforward because it might not be possible to simply move each car directly into its final position. One possibility: drive all the cars (simultaneously) around a very long circular track and keep adding new cars when permitted by the order. The problem: towards the end of this process, almost all cars are running, so we are expending O(N) fuel for each new car added. We could recursively split all the cars into two such rings, and then merge the rings; this is equivalent to a binary merge sort. (I wasn't actually working on cars, but they seemed to be large enough & massive enough that their movement was far more expensive than all but the most exhaustive calculations.) Perhaps a better analogy is rearranging the cars on a railroad train? We have to get the train cars into a proper order, but the only way seems to be cutting the train and putting some of the cars onto sidings and sliding the rest of the train by them and then reinserting them. So we have some limit on the number of parallel sidings, so we can't simply separate the train into 10,000 parallel sidings. We might also have a limit on the number of sidings around the circular track -- 10,000 such sidings might also be excessive. Perhaps there is a clever dynamic programming scheme that could cut down the work to polynomial time w/o losing too much in rearrangement efficiency. Otherwise, we still have N! orders of rearrangement to consider. At 11:44 AM 4/20/2018, Marc LeBrun wrote:
If preprocessing is truly free, then at worst you need only simulate each of the N different scenarios without actually moving the associated data and see which one would be cheapest. (ie run through the cases, for k=0..N-1, simulating sorting the permutation using the predicates Pk := i < j just when (i-k)\N < (j-k)\N)
Perhaps for a specific sorting algorithm you can compute the merit for each Pk more directly, without actually undertaking the simulation, thus being cheaper than free.
On Apr 20, 2018, at 11:14 AM, Henry Baker <hbaker1@pipeline.com> wrote: Yes, a radix-style sort will work; I had forgotten about that.
I'm working on a model where every access is expensive, and RAM access is not even remotely constant time.
In this particular problem, I can *preprocess for free* to determine the complete permutation, but then I have to pay full retail price for actually applying this permutation to rearrange the data records.
I was hoping to minimize rearrangements in the cases where the data was already "almost sorted".
I was thinking along the lines of Quicksort, which is pretty good when the data is already almost sorted.
At 10:05 AM 4/20/2018, Tomas Rokicki wrote:
A linear walk can notice and preserve the cyclic walk else abort. For what disorder distribution do you want to do better?
If you have such a field as you describe radix sort is linear time, as discussed in TAOCP.
On Fri, Apr 20, 2018 at 12:56 PM Henry Baker <hbaker1@pipeline.com> wrote:
Suppose you have N records in which one of the fields is a number 0..(N-1), and there is exactly one record for each number 0..(N-1).
It is trivial to sort such a set using traditional Knuth-TAOCP algorithms.
However, if I don't care that the first record is labelled "0", but only care that the final ordering preserves the *cyclic* ordering of the group, can I do any better?
Obviously, I can't do a lot better, since cyclicly rotating the ordering costs O(N), while sorting costs O(NlogN), but is there a clever way to sort w/o putting "0" at the front and "(N-1)" at the end? In particular, is there a way to sort that automatically notices when the records are already in cyclic order, and doesn't bother making any further changes. -- http://cube20.org/ -- http://golly.sf.net/ --
I think we need some sort of explicit cost model here. Otherwise we are each blindly touching a different part of the elephant. On Fri, Apr 20, 2018 at 3:40 PM Henry Baker <hbaker1@pipeline.com> wrote:
Yes, we could (in theory) simulate every possible permutation, which might be worth it -- e.g., suppose we have N=10,000 cars to arrange in a cyclic order, but we eventually have to physically move them into position; moving them into position might not be straightforward because it might not be possible to simply move each car directly into its final position.
One possibility: drive all the cars (simultaneously) around a very long circular track and keep adding new cars when permitted by the order. The problem: towards the end of this process, almost all cars are running, so we are expending O(N) fuel for each new car added.
We could recursively split all the cars into two such rings, and then merge the rings; this is equivalent to a binary merge sort.
(I wasn't actually working on cars, but they seemed to be large enough & massive enough that their movement was far more expensive than all but the most exhaustive calculations.)
Perhaps a better analogy is rearranging the cars on a railroad train? We have to get the train cars into a proper order, but the only way seems to be cutting the train and putting some of the cars onto sidings and sliding the rest of the train by them and then reinserting them. So we have some limit on the number of parallel sidings, so we can't simply separate the train into 10,000 parallel sidings. We might also have a limit on the number of sidings around the circular track -- 10,000 such sidings might also be excessive.
Perhaps there is a clever dynamic programming scheme that could cut down the work to polynomial time w/o losing too much in rearrangement efficiency. Otherwise, we still have N! orders of rearrangement to consider.
At 11:44 AM 4/20/2018, Marc LeBrun wrote:
If preprocessing is truly free, then at worst you need only simulate each of the N different scenarios without actually moving the associated data and see which one would be cheapest. (ie run through the cases, for k=0..N-1, simulating sorting the permutation using the predicates Pk := i < j just when (i-k)\N < (j-k)\N)
Perhaps for a specific sorting algorithm you can compute the merit for each Pk more directly, without actually undertaking the simulation, thus being cheaper than free.
On Apr 20, 2018, at 11:14 AM, Henry Baker <hbaker1@pipeline.com> wrote: Yes, a radix-style sort will work; I had forgotten about that.
I'm working on a model where every access is expensive, and RAM access is not even remotely constant time.
In this particular problem, I can *preprocess for free* to determine the complete permutation, but then I have to pay full retail price for actually applying this permutation to rearrange the data records.
I was hoping to minimize rearrangements in the cases where the data was already "almost sorted".
I was thinking along the lines of Quicksort, which is pretty good when the data is already almost sorted.
At 10:05 AM 4/20/2018, Tomas Rokicki wrote:
A linear walk can notice and preserve the cyclic walk else abort. For what disorder distribution do you want to do better?
If you have such a field as you describe radix sort is linear time, as discussed in TAOCP.
On Fri, Apr 20, 2018 at 12:56 PM Henry Baker <hbaker1@pipeline.com> wrote:
Suppose you have N records in which one of the fields is a number 0..(N-1), and there is exactly one record for each number 0..(N-1).
It is trivial to sort such a set using traditional Knuth-TAOCP algorithms.
However, if I don't care that the first record is labelled "0", but only care that the final ordering preserves the *cyclic* ordering of the group, can I do any better?
Obviously, I can't do a lot better, since cyclicly rotating the ordering costs O(N), while sorting costs O(NlogN), but is there a clever way to sort w/o putting "0" at the front and "(N-1)" at the end? In particular, is there a way to sort that automatically notices when the records are already in cyclic order, and doesn't bother making any further changes. -- http://cube20.org/ -- http://golly.sf.net/ --
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
= Henry Baker <hbaker1@pipeline.com> Yes, we could (in theory) simulate every possible permutation,
I think you misread me a little. To clarify: I didn't say "simulate every possible permutation", which would be N! cases, but only "simulate sorting every *rotation*" of the target output permutation, which would only be N cases. Then, when you've pre-determined "offline" which case would be cheapest, you go back and apply the manipulations done in that simulation to the actual train "online". Total cost = N * cost-of-offline-simulated-sort + 1 * cost-of-online-real-sort
participants (4)
-
Henry Baker -
Marc LeBrun -
Tomas Rokicki -
Wouter Meeussen