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

Re: Short circuiting sort

From:
Glenn Linderman
Date:
June 25, 2004 08:53
Subject:
Re: Short circuiting sort
Message ID:
40DC4AE3.9080300@nevcal.com
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 <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

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 -- http://nevcal.com/
===========================
The best part about procrastination is that you are never bored,
because you have all kinds of things that you should be doing.




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