[Tim]
>> .... If the result of Python's sort is
>>
>> [x, y]
>>
>> then I happen to know (because I know everything about its
>> implementation) that one of two things is true:
>>
>> - The original list was also [x, y], and y < x was False.
[Steven]
> That's my reasoning, based on your earlier example with the list of
> three sets.
>> But we
>> can't deduce anything about what x < y, x <= y, x == y, x != y. x > y,
>> x >= y, y <= x, y > x, y >= x, y == x, or y != x would do.
> This doesn't surprise me, because comparison methods are independent of
> each other and the law of trichotomy doesn't necessarily hold.
The code doesn't even assume that x == x holds - or that x < y will
return the same value if called a second time. When user-supplied
operators are called, nothing can be assumed. This isn't empty ;-)
There's a long history of segfaults due to assuming _any_ kind of
sanity in user-supplied code.
>> - The original list was [y, x], and x < y was True (but again we can't
>> deduce anything about what any other comparisons involving x and y
>> would do).
> Now *that* surprises me!
>
> Should I understand from this that the direction of comparisons (whether
> timsort compares `x < y` or `y < x`) could be chosen arbitrarily?
I'm not sure what this is about. In both cases above, I'm referring
to elements by their names in the second (output) list, but they're
treated exactly the same way in the original list. If the list is
named, say, "values", the only comparison done is
values[1] < values[0]
If that's True, the values are swapped; if False, they're left alone.
> My understanding was that the direction of comparisons was controlled by
> the reverse parameter.
If reverse=True is passed,
values[1] < values[0]
is _still_ the only comparison done (although, as about to be
explained, the elements are swapped _before_ the sort sees them).
`reverse` has no effect whatsoever on any internal step of the
algorithm. Instead it's a pre/post-processing gimmick:
values.sort(reverse=True)
acts like, and is actually _implemented_ as:
values.reverse()
values.sort()
values.reverse()
This is subtle, and the docs could be clearer about what it means by
"as if each comparison were reversed", I didn't write that (I didn't
implement "reverse=" either). but appreciate that what it's trying to
say is subtle. It's NOT the same as:
values.sort()
values.reverse()
and in my experience barely anyone knows why. It's to make
list.sort() stable even if reverse=True is passed: equal items remain
in the their original order regardless of the value of the reverse
flag. The second shorter spelling would violate stability, but the
first longer spelling preserves it (the order of equal items is first
reversed, then the stable regular sort preserves that reversed order,
and then the final reverse restores the original order of equal
items).
> So if we're referring only to the default
> reverse=False, the comparisons must go in one direction rather than the
> other. Is that wrong?
Still not clear what the question is, but hope the above answered it.
In particular, the reverse flag is mostly a red herring.
>> For longer lists it can get much more complicated; comparing adjacent
>> elements is just the first step in an algorithm with several stages,
>> which dynamically adjust to patterns of comparison outcomes that are
>> discovered as the algorithm goes along.
> Ack. But my expectation is that by the time all the complicated stuff
> was done, we might not know all the gory details of what elements got
> compared, and we don't know anything about any "global" order over the
> entire set, but we do know the "local" order: if x ends up next to y,
> then *at some point* in the sorting x must have been compared to y
> and so we know that y doesn't compare less than x.
>
> Is this not accurate?
I really don't know! It sounds plausible ;-) , for the current sort
implementation, which is a mix of strategies mostly based on binary
search and merging. Offhand I couldn't think of a counterexample -
but their was no _intent_ to make that so.
It's not true of sorts in general. For an easy example, here's a
simple stable(!) quicksort, based on 3-way partitioning (extremely
effective in the presence of many equal elements):
def quick3(xs):
from random import choice
if len(xs) <= 1:
return xs
lt = []
eq = []
gt = []
pivot = choice(xs)
for x in xs:
if x is pivot or x == pivot: # "is" to guard against insane __eq__
eq.append(x)
elif x < pivot:
lt.append(x)
else:
gt.append(x)
return quick3(lt) + eq + quick3(gt)
Pass it the list
[1, 2a. 2b. 2c. 3]
where the three instances of "2" are tagged with letters so we can
visually distinguish them. If the pivot is 2b, then the only
comparisons ever done involve 2b, the output list is the same, but 1
is never compared with 2a nor is 2c ever compared with 3.
_______________________________________________
Python-ideas mailing list -- python-ideas@python.org
To unsubscribe send an email to python-ideas-le...@python.org
https://mail.python.org/mailman3/lists/python-ideas.python.org/
Message archived at
https://mail.python.org/archives/list/python-ideas@python.org/message/WMGVVC3OVWUIG7ALPHKE3BVNPC3U4D3U/
Code of Conduct: http://python.org/psf/codeofconduct/
