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

Re: Short circuiting sort

From:
John P. Linderman
Date:
June 25, 2004 04:29
Subject:
Re: Short circuiting sort
Message ID:
200406251128.HAA13560@raptor.research.att.com
>Cc: Glenn Linderman <perl@nevcal.com>, Nick Ing-Simmons <nick@ing-simmons.net>
>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



nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About