Сортировка экземпляров классов в Python

Question

Что использует Python 2.7 для сортировки экземпляров класса vanilla?Меня интересует поведение сортировки по умолчанию.

Предположим, у меня есть класс

class S():
    pass

Затем я могу создать пару экземпляров и отсортировать их:

a = S(); b = S(); c = S()
l = [(a,'a'), (b,'b') ,(c, 'c')]
sorted(l)

Это напечатает некоторую сортировку объектов.Теперь у меня есть вопрос из двух частей:

• Использует ли python объекты __hash__() и, следовательно, их id()?
• Можно ли переопределить __hash__(), чтобы повлиять на поведение сортировки?

Answer 1

Встроенная сортировка Python 3 использует метод __lt__ в вашем классе.

Методы расширенного сравнения являются особенными в Python, поскольку они могут возвращать специальный тип NotImplemented, если его нет.__lt__ определено - взгляните на документы на этой странице: http://docs.python.org/reference/datamodel.html#the-standard-type-hierarchy

Поскольку истинное значение NotImplemented равно True, любое логическое сравнение, которое получает NotImplemented, будет продолжаться, как если быпервый элемент на самом деле меньше второго, что приведет к тому, что сортировка покинет список в том же порядке, в каком она была.

Посмотрите на интерактивную оболочку.Вы можете видеть, как значения истинности будут использоваться в сортировке, и что Python считает, что оба объекта меньше друг друга:

>>> class S():
...     pass
...
>>> a = S()
>>> b = S()
>>> a.__lt__( b )
NotImplemented
>>> if a.__lt__( b ):
...     print( "derp!" )
...
derp
>>> if b.__lt__(a):
...     print( "derp" )
...
derp

Вот еще несколько ссылок:

• Метод __lt__ (неофициальный справочник по Python)
• Сортировка мини-инструкции
• Встроенные константы

РЕДАКТИРОВАТЬ: После просмотра Python 2.7 похоже, что идентификатор объектов используется для сортировки, а метод __lt__ не определен для простого класса, кактвой пример.Извините за путаницу.

Answer 2

Алгоритм сортировки Python сравнивает элементы исключительно с использованием теста «меньше чем», который может быть реализован с использованием специального метода __cmp__() (теперь не рекомендуется) или __lt__() в классе.

При отсутствиилюбой конкретной инструкции о том, как сравнивать два объекта, id() используется (не хеш) для объектов того же типа, что и в вашем случае.

Answer 3

Я попробовал ваш пример на своей машине (python 2.7):

>>> sorted(l)
[(<__main__.S instance at 0x107142a70>, 'a'), (<__main__.S instance at 0x107142ab8>, 'b'), (<__main__.S instance at 0x107142b00>, 'c')]

Обратите внимание, что отсортированный список имеет порядок id():

>>> id(a)
4413729392
>>> id(b)
4413729464
>>> id(c)
4413729536

Если я генерирую хэши, я получаю:

>>> hash(a)
275858087
>>> hash(b)
-9223372036578917717
>>> hash(c)
275858096

Что говорит о том, что сортировка не на основе хеша.

См. Ответ Дерекердмана о том, как заставить Python сортировать ваш класс так, как вы хотите.

Редактировать: Кстати, если вы поместите элементы в список в обратном порядке, а затем отсортируете, вы получите:

>>> l = [(c,'c'), (b, 'b'), (a, 'a')]
>>> sorted(l)
[(<__main__.S instance at 0x107142a70>, 'a'), (<__main__.S instance at 0x107142ab8>, 'b'), (<__main__.S instance at 0x107142b00>, 'c')]

Еще раз, он отсортирован в порядке id().