[Python-Dev] Re: Re: lists v. tuples

Tim Peters tim.one@comcast.net
Tue, 15 Apr 2003 21:57:49 -0400


[Andrew Koenig]
> Yes, I know that -1 is a valid truth value.
>
> So the first time you care is the first time f(x, y) returns nonzero.
> Now you can find out what kind of function f is by calling f(y, x).
> If f(y, x) returns zero, f is <.  Otherwise, it's a 3-way comparison.

[Greg Ewing]
> I think the worry is that the function might be saying
> "true" to both of these, but just happen to spell it
> 1 the first time and -1 the second.

Then it's answering true to both

    x < y ?
and
    y < x ?

The comparison function is insane, then, so it doesn't matter what
list.sort() does in that case (the algorithm is robust against insane
comparison functions now, but doesn't define what will happen then beyond
that the output list will contain a permutation of its input state).

I've ignored this scheme for two reasons:  anti-Pythonicity (having Python
guess which kind of comparison function you wrote is anti-Pythonic on the
face of it), and inefficiency.  list.sort() is so bloody highly tuned now
that adding even one test-&-branch per comparison, in C, on native C ints,
gives a measurable slowdown, even when the user passes an expensive
comparison function.  In the case that no comparison function is passed,
we're able to skip a layer of function call now by calling
PyObject_RichCompareBool(X, Y, Py_LT) directly (no cmp-to-LT conversion is
needed then).

Against that, it could be natural to play Andrew's trick only in count_run()
(the part of the code that identifies natural runs).  That would be confined
to 2 textual comparison sites, and does no more than len(list)-1 comparisons
total now.