Sorting (not Python-specific)
Tim Peters
tim.one at home.com
Sun Nov 4 06:00:49 CET 2001
[Marcin 'Qrczak' Kowalczyk]
> What are advantages and disadvantages in parametrizing sorting either
> by '<' or by the 3-way comparison?
Primarily cultural, I think: depending on which one you pick, you'll
confuse either C or Lisp programmers. Python's internals are in an odd
state now, where for backward compatibility a comparison function passed to
list.sort() must follow the 3-way scheme, but the sorting routine only asks
"less than 0, or not?", i.e. "__lt__, true or false?" is the only comparison
outcome it wants. And objects that support *only* __lt__ comparison sort
fine by default:
>>> class C:
... def __init__(self, n):
... self.n = n
... def __lt__(x, y):
... print "asked %d < %d?" % (x.n, y.n)
... return x.n < y.n
... def __cmp__(x, y):
... print "OOPS!"
...
>>> x = map(C, range(10))
>>> import random
>>> random.shuffle(x)
>>> x.sort()
asked 5 < 7?
asked 5 < 7?
asked 2 < 7?
asked 2 < 5?
asked 9 < 5?
asked 9 < 7?
asked 6 < 7?
asked 6 < 5?
asked 8 < 6?
asked 8 < 9?
asked 8 < 7?
asked 0 < 7?
asked 0 < 5?
asked 0 < 2?
asked 3 < 6?
asked 3 < 2?
asked 3 < 5?
asked 4 < 6?
asked 4 < 3?
asked 4 < 5?
asked 1 < 5?
asked 1 < 3?
asked 1 < 2?
asked 1 < 0?
>>>
Note that if huge masses of equal elements are an expected case, you may
*want* to use a 3-way scheme for clarity and efficiency inside the sorting
routine. Indeed, Python's internal sort does a bit of "OK, it was not the
case that x < y, and also not the case that y < x, therefore if this
ordering is sane for sorting at all, it must be the case both that x >= y
and y >= x, so that x == y" deduction. But there's *just& "a bit" of that,
and using equality-testing too wouldn't speed it up.
if-equality-is-a-slippery-concept-then-so-is-inequality-ly y'rs - tim
More information about the Python-list
mailing list