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 2681Thread Previous | Thread Next