On Wed, 28 Mar 2001 11:11:20 -0500, Dan Sugalski wrote:
> "Can perl automatically optimize away function and tie calls inside
> a sort function, and under what circumstances?"
>
>It doesn't really matter if the functions inside the sort function are
>idempotent--what matters is whether it's OK for us to go and memoize the
>things (or whatever else we might choose to do)
Exactly. This whole discussion borders on the edge of the ridiculous.
Any sort algorithm ALWAYS assumes that comparisons are constant, i.e.
return consequent results on subsequent calls. They always infer sorting
information out of what they got yet. That's why they hardly ever need
to compare every item with every other item. The fewser comparisons, the
better the algorithm.
As MJD very recently wrote:
>An optimal sort function will not call the comparator if it
>already knows what the result should be!
So true.
That implies that side effects and otherwise unmemoizability of sort
functions may *always* safely be ignored. If not, the programmer has a
personal problem, i.e. a bad starting point. Otherwise, the results of
sort would largely depend upon which sort algorithm was used internally!
--
Bart.
