From:

Date:

July 8, 2004 19:51Subject:

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

1089341440.996.323.camel@plaza.davidnicol.comOn Thu, 2004-07-08 at 21:14, david nicol wrote: > After finding runs, we can find the M best with M*R more comparisons. > Which may or may not be an improvement over a NlogM single pass. How > big do the numbers have to be before it's worth the expected 1.5*N > comparisons to find out how small R is, given that after determining R > we can still fall back to the single pass when M*R is larger than NlogM? while collecting runs we can give up on the whole deal when we have too many runs. Too many runs is : M*R > NlogM R > (NlogM)/M so, calculate that, then collect runs, if we make it through the whole array with fewer, shift elements off of runs, otherwise do a single pass with binary insertions. I'm sure everyone is sick of me posting less-than-fully-baked postings by now, I thank you for your continuing indulgence. -- david nicol "cat and buttered toast"Thread Previous | Thread Next

- 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 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 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
- 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: [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