develooper Front page | perl.perl5.porters | Postings from June 2004

Re: Short circuiting sort

Glenn Linderman
June 25, 2004 08:53
Re: Short circuiting sort
Message ID:
On approximately 6/25/2004 4:28 AM, came the following characters from
the keyboard of John P. Linderman, and is responded to by "the other 
Linderman" who remembers encountering this one in a former position at a 
former subsidiary of this one's corporation:
>>Cc: Glenn Linderman <>, Nick Ing-Simmons <>
>>David Nicol replied to the other Linderman:
>>On Sun, 2004-06-20 at 14:49, Glenn Linderman wrote:
>>>So, in the situation where you have a countable number of parameters as 
>>>the target of the sort, such as your example, or
>>>   ($first, $second, $third, $fourth) = sort @ary;  # only sort 4 entries
>>>   @most[ 0 .. 6 ] = sort @ary; # only sort 7 entries
>>>the compiler could derive the hint, in a similar manner as it presently 
>>>(recent feature) derives the in-place optimization.
>>Yes, exactly.  We would begin by providing the hint for the simple cases
>>and gradually exapnd the range of optimized situations .  I
>>imagine a working intermediate stage where your first example is
>>optimized and your second is not, but maybe the second is already
>>optimized to
>> ($most[0],$most[1],$most[2],$most[3],$most[4],$most[5],$most[6]) = ...
>>at some level, in which case we could get them both at the same time.
> I can kind of imagine how merge sort and quicksort could benefit
> from knowing that only the "top N" elements were needed (runs
> longer than N could be truncated in mergesort, partitions following
> the first N elements could be dropped).  Certain to make things
> uglier, and probably hard to do without adversely impacting full
> sorts, unless a lot of code gets duplicated.  Qsort would probably
> be easier to jigger to take advantage, but if you want to preserve
> stability, you end up paying a penalty in space.  Seems harmless
> to make the hint available, though.  It can simply be ignored until
> a clever implementation pops up.  -- jpl

So in terms of N items in the array and M items desired...

One trivial way to take advantage of the hint is to recall that the 
lowly N-squared bubble sort (and variations) produces one high (or low) 
value per pass, and that for small M and large N, that M*N is smaller 
than N lg N.

Glenn --
The best part about procrastination is that you are never bored,
because you have all kinds of things that you should be doing. Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About