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

Re: optimizing Short circuiting sort method based on [M]

Paul Fenwick
July 8, 2004 20:09
Re: optimizing Short circuiting sort method based on [M]
Message ID:
G'day David / P5Ps,

david nicol wrote:

>     sub Lazy::Sort::TIEARRAY{

Module names should go from general to specific.  Hence 'Sort::Lazy' may 
be a better choice.  (This also lines up nicely with all the other 
Sort::* modules on CPAN.

>     sub Lazy::Sort::SHIFT{
>         wantarray and eval{Games::Roguelike::Nethack::play()};   


> Finding the hints is the other half of the problem.  I've seen several
> identifiable cases so far:

I *really* like the idea of a lazy sort, where each element is produced 
on demand.  However I believe that it's different to a 'truncated sort', 
where we can throw away all but the top M elements.

In a lazy sort, we may be asked to produce the entire sorted list, 
sooner or later, we can't throw away any elements.  For a truncated 
sort, we know that we're never going to asked more than M.  A truncated 
sort definitely allows you to run much faster, using my suggestion of 
discarding elements in Quicksort, or Ton's suggestion of truncating runs 
in Mergesort.

The two sorts have different applications, too.  Truncated sorts are 
perfect for 'top 10' style lists.  Lazy sorts are ideal when you wish to 
go through elements in a sorted order, but have a good reason to believe 
that you may stop early, but don't know in advance at which element you 
wish to stop.

I would be impressed if you can do better than heap-sort for a lazy 
sort.  It seems ideal for the job, as it produces exactly one sorted 
element each iteration, and runs in NlogN time.  There are a few 
efficient algorithms out there as well.

I do think that your merge sort has merit for truncated sort.  I just 
don't know a good way of passing in hints.  ;(



Paul Fenwick <> |
Director of Training                   | Ph:  +61 3 9354 6001
Perl Training Australia                | Fax: +61 3 9354 2681 Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About