Front page | perl.perl5.porters |
Postings from July 2004
G'day David / P5Ps,
david nicol wrote:
> sub Lazy::Sort::TIEARRAY{
<pedant>
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.
</pedant>
> sub Lazy::Sort::SHIFT{
>
> wantarray and eval{Games::Roguelike::Nethack::play()};
(*chuckles*)
> 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. ;(
Cheers,
Paul
--
Paul Fenwick <pjf@perltraining.com.au> | http://perltraining.com.au/
Director of Training | Ph: +61 3 9354 6001
Perl Training Australia | Fax: +61 3 9354 2681