dpuu dave-at-whipp.name |Perl 6| wrote:
On Aug 30, 8:47 am, [EMAIL PROTECTED] (John M. Dlugosz) wrote:
Have the sort function simply return a lazy list object. When the [4]
is called on that object, it knows to do as much work as needed, and can
leave the rest as lazy.
That may be half the answer, but simply making the decision lazily is
insufficient, because the guarantee that only exactly one item is
needed is lost. An algorithm that singles out exactly one ordered
element may be in retrospect inefficient if the list is later accessed
for other indices.
At some point you have to just say what you want: call a function to
return the nth item instead of sorting the whole thing and throwing most
of it away. Look for it in CPAN. As I recall, in a Masters level
algorithms class we spent a whole semester proving that this could be
done in O(n) time, just like the special cases of finding the first and
last elements.
If it were a common thing to do, then the implementation could optimize
the expression. But if it were really that common, there would be a C
function for that with a old name we'd all know about. Perhaps the
supplier of the CPAN module for the nth function could also include,
besides the actual function, an optimization pattern plug-in that
locates the idiom in the parse tree and replaces the expression with a
call to nth.
--John
