Front page | perl.perl5.porters |
Postings from June 2004
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.