From:

Date:

July 5, 2004 17:33Subject:

Re: optimizing Short circuiting sort method based on [M]Message ID:

1089074003.1003.111.camel@plaza.davidnicol.comOn Wed, 2004-06-30 at 03:18, Paul Fenwick wrote: > Glenn Linderman wrote: > > > As an alternative to the copy cost above, I posit an algorithm I'll call > > scan-select (maybe someone has a name for it) where the original data > > isn't modified, but on the first pass you go through all N entries and > > look for the highest/lowest number, and keep track of where it was, and > > select it. Then on each subsequent scan you go through all the data > > that hasn't already been selected, and look for the highest/lowest > > number, and select it, until you have accumulated M entries. This would > > This sounds just like Selection Sort to me, although stopping after you > have the required number of elements. It's O(N^2), although in this > case it would be O(N*M). > In the case where M approaches N, Selection Sort will be a very poor > choice, and we'd be better off using an O(N*logN) sort and then > returning only the wanted elements. I am wondering if I was somehow unclear in my proposed algorithm, archived at http://www.xray.mpe.mpg.de/mailing-lists/perl5-porters/2004-06/msg00592.html which describes both bubble and inserting to place new elements in the short list. I believe the algorithm there to be worst case N*M for bubble and N lg M for insertion placement mechanisms. Expected case for random data should be the sum of: M lg M # sort the first M elements N - M # the comparison of each element to the current gatekeeper element # a term that represents the base two log of M-1 multiplied by the probability that an element will compare left of the gatekeeper element, which itself gets adjusted left as the long array is traversed. The probability of an element belonging leftward from the gatekeeper falls to M/N for the last element considered, from some larger amount that represents the probability of $Large[$M] sorting leftward of the rightmost element in a @Short = sort @Large[0..(M-1)]. My grasp of combinatorics is currently not up to describing that term. And that's without considering the effect of stability in preventing placements of elements that are merely equivalent to the gatekeeper instead of leftward of it. Important points: * One pass over all elements in long array, comparing each to the "gatekeeper" element which is the leftmost element in the short array. * Additional comparisons are only required to determine placement of an element that belongs left of the gatekeeper. * We are only concerned with optimizing away unncessary sorting when M is smaller than N. * we only consider comparisons as the metric. After the short circuiting sort optimization is in place a hint about when the comparison function is cheap enough that we should care about all the data shifting required for insertion sorts and reoptimize short circuited sorts back to full sorts for sufficiently large M and sufficiently small N-M -- david nicol "cat and buttered toast"

- sort in scalar context, but broken due to inexperience. by David Nicol
- Re: sort in scalar context, but broken due to inexperience. by Dave Mitchell
- Re: sort in scalar context, but broken due to inexperience. by hv
- Re: sort in scalar context, but broken due to inexperience. by david nicol
- Re: sort in scalar context, but broken due to inexperience. by merlyn
- Re: sort in scalar context, but broken due to inexperience. by Rafael Garcia-Suarez
- [PATCH] sort plays nethack in a scalar context (was: sort in scalarcontext, but broken due to inexperience.) by Paul Fenwick
- Re: [PATCH] sort plays nethack in a scalar context (was: sort inscalar context, but broken due to inexperience.) by Rafael Garcia-Suarez
- Re: [PATCH] sort plays nethack in a scalar context by Paul Fenwick
- Re: [PATCH] sort plays nethack in a scalar context by Nicholas Clark
- Re: [PATCH] sort plays nethack in a scalar context by H.Merijn Brand
- Re: [PATCH] sort plays nethack in a scalar context by Nicholas Clark
- Re: [PATCH] sort plays nethack in a scalar context (was: sort in scalar context, but broken due to inexperience.) by merlyn
- Re: sort in scalar context, but broken due to inexperience. by Graham Barr
- Re: sort in scalar context, but broken due to inexperience. by Dave Mitchell
- Re: sort in scalar context, but broken due to inexperience. by Nick Ing-Simmons
- Short circuiting sort by David L. Nicol
- Re: Short circuiting sort by Glenn Linderman
- Re: Short circuiting sort by david nicol
- Re: sort in scalar context, but broken due to inexperience. by david nicol
- Re: sort in scalar context, but broken due to inexperience. by Graham Barr
- RE: optimizing Short circuiting sort method based on [M] by Orton, Yves
- Re: optimizing Short circuiting sort method based on [M] by Glenn Linderman
- Re: optimizing Short circuiting sort method based on [M] by John P. Linderman
- Re: optimizing Short circuiting sort method based on [M] by david nicol
- Re: optimizing Short circuiting sort method based on [M] by Paul Fenwick
- Re: optimizing Short circuiting sort method based on [M] by david nicol
- Re: optimizing Short circuiting sort method based on [M] by John P. Linderman
- Re: optimizing Short circuiting sort method based on [M] by Nicholas Clark
- Re: optimizing Short circuiting sort method based on [M] by david nicol
- more 5.9 sort tests by david nicol
- Re: more 5.9 sort tests by Rafael Garcia-Suarez
- Re: more 5.9 sort tests by david nicol
- Re: more 5.9 sort tests by Nicholas Clark
- Re: more 5.9 sort tests by Rafael Garcia-Suarez
- Re: more 5.9 sort tests by Ronald J Kimball
- Re: more 5.9 sort tests (second draft) by david nicol
- Re: more 5.9 sort tests (second draft) by Rafael Garcia-Suarez
- Re: optimizing Short circuiting sort method based on [M] by Nicholas Clark
- Re: optimizing Short circuiting sort method based on [M] by Nicholas Clark
- Re: optimizing Short circuiting sort method based on [M] by david nicol
- Re: optimizing Short circuiting sort method based on [M] by Nicholas Clark
- Re: optimizing Short circuiting sort method based on [M] by david nicol
- Re: optimizing Short circuiting sort method based on [M] by Dave Mitchell
- Re: optimizing Short circuiting sort method based on [M] by david nicol
- Re: optimizing Short circuiting sort method based on [M] by Paul Fenwick
- Re: optimizing Short circuiting sort method based on [M] by Nicholas Clark
- Re: optimizing Short circuiting sort method based on [M] by John P. Linderman
- RE: [PATCH] sort plays nethack in a scalar context by Orton, Yves
- Re: [PATCH] sort plays nethack in a scalar context by Abigail
- Re: [PATCH] sort plays nethack in a scalar context by Rafael Garcia-Suarez
- Re: [PATCH] sort plays nethack in a scalar context by Ovid
- Re: [PATCH] sort plays nethack in a scalar context by Nicholas Clark
- Re: [PATCH] sort plays nethack in a scalar context by david nicol
- Re: Short circuiting sort by John P. Linderman
- Re: Short circuiting sort by Glenn Linderman
- Re: Short circuiting sort by david nicol
- Re: optimizing Short circuiting sort method based on [M] by david nicol
- Re: optimizing Short circuiting sort method based on [M] by Glenn Linderman
- Re: optimizing Short circuiting sort method based on [M] by david nicol
- Re: optimizing Short circuiting sort method based on [M] by Paul Fenwick
**Re: optimizing Short circuiting sort method based on [M]**by david nicol- Re: optimizing Short circuiting sort method based on [M] by Paul Fenwick
- Re: optimizing Short circuiting sort method based on [M] by Glenn Linderman
- Re: optimizing Short circuiting sort method based on [M] by Glenn Linderman
- Re: optimizing Short circuiting sort method based on [M] by perl5-porters
- Re: optimizing Short circuiting sort method based on [M] by Glenn Linderman
- Re: optimizing Short circuiting sort method based on [M] by Nicholas Clark
- Re: optimizing Short circuiting sort method based on [M] by Glenn Linderman
- Re: optimizing Short circuiting sort method based on [M] by david nicol
- Re: optimizing Short circuiting sort method based on [M] by Dave Mitchell
- Re: optimizing Short circuiting sort method based on [M] by david nicol
- Re: optimizing Short circuiting sort method based on [M] by Dave Mitchell
- Re: optimizing Short circuiting sort method based on [M] by Paul Fenwick
- Re: optimizing Short circuiting sort method based on [M] by david nicol
- Re: optimizing Short circuiting sort method based on [M] by perl5-porters
- Re: optimizing Short circuiting sort method based on [M] by Glenn Linderman

nntp.perl.org: Perl Programming lists via nntp and http.

Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About