On Wed, 03 Apr 2013 07:52:42 -0400, Dave Angel wrote:
I thought that the sort algorithm used a hash of all
the items to be sorted, and only reverted to a raw comparison of the
original values when the hash collided. Is that not the case? Or is
the code you post here only used when the hash collides?
Sorting does not require that the elements being sorted are hashable.
If I have understood the implementation here:
http://hg.python.org/releasing/3.3.1/file/2ab2a09901f9/Objects/listobject.c
sorting in Python only requires that objects implement the less-than
comparison.
py class Funny:
... def __init__(self, x):
... self.x = x
... def __lt__(self, other):
... return self.x other.x
... def __gt__(self, x):
... raise AttributeError
... __le__ = __ge__ = __eq__ = __ne__ = __gt__
...
py L = [Funny(i) for i in range(10)]
py random.shuffle(L)
py [f.x for f in L]
[8, 5, 7, 0, 9, 2, 3, 6, 1, 4]
py [f.x for f in sorted(L)]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
but if I change Funny.__lt__ to also raise, sorting fails.
I seem to recall that sort relies only on operator is a language
promise, but I can't seem to find it documented anywhere official.
--
Steven
--
http://mail.python.org/mailman/listinfo/python-list
