From:

Date:

June 20, 2004 01:31Subject:

Short circuiting sortMessage ID:

40D50DD9.3000803@umkc.eduNick Ing-Simmons wrote: >(I would still like sort in scalar context to return min or max value > - don't care which because one can change cmp function to get the other.) > Currently ($first) = sort @ary; gives the first of the sorted list, after doing a mess of extra work. If C<sort> were to take a hint indicating how many results are going to be used, similar to the fourth argument of C<split> but determined by parsing appropriate l-values, sort algorithms that ignore the rest of the array could be used. Worst case would be l*n comparisons when l is how many values you want returned and n is array size, and it could be turned into n log l by using a binary system to locate a earlier value within the set of values that will be returned. Since the above code works, a sensible thing for sort in scalar to do would be to treat the l-value as if it was a singleton array, making $first = sort @ary; and ($first) = sort @ary; equivalent. The scalar version could do a simple short-circuit minimum function (n-1 comparisons) until the mechanisms for communicating L-value array size are hammered out. >What can one use your sortedness value for? > * you can sort arrays based on how sorted they are, for instance when deciding what to do next * you can determine an sortedness threshold above which you consider your data "sorted enough" to not bother with an expensive sort * if the sortedness pass cached its result as the first pass of the merge sort, code such as @ary = sort @ary if sort( @ary ) < 0.95; would take n-1 comparisons except when a sort is required. * It'll make Randall Schwartz call my C coding "Amazing" which I can use on the back covcer of my paperback

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

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

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