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

Re: Short circuiting sort

John P. Linderman
June 25, 2004 04:29
Re: Short circuiting sort
Message ID:
>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 Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About