Python 3 排序忽略 __lt__ 和 __eq__

Question

我在 64 位 Windows 上使用 Python 3.5.1。我的问题是 Python 在排序时似乎忽略了用户定义类上的 __eq__ 和 __lt__ 运算符。在尝试对包含此类实例的元组进行排序时，使用自定义排序键是一种不起作用的解决方法。

例子:

class Symbol:
  def __init__(self, name, is_terminal = False):
    self.name = name
    self.is_terminal = is_terminal
  def __eq__(self, other):
    return (self.is_terminal, self.name) == (other.is_terminal, other.name)
  def __lt__(self, other):
    return (self.is_terminal, self.name) < (other.is_terminal, other.name)

symbols = set()
for s in "abcdef":
  symbols.add(Symbol(s))

sorted_symbols = sorted(symbols)
# sorted_symbols now contain the symbols in random order

使用 functools.total_ordering 装饰器没有帮助。

我的问题是如何在 Python 3 中定义用户类的顺序？

Answer 1

Python 确实不会忽略__eq__ 和__lt__，至少在您实际使用@functools.total_ordering 时不会:

>>> from functools import total_ordering
>>> @total_ordering
... class Symbol:
...     def __init__(self, name, is_terminal=False):
...         self.name = name
...         self.is_terminal = is_terminal
...     def __repr__(self):
...         return 'Symbol({0.name!r}, is_terminal={0.is_terminal!r})'.format(self)
...     def __hash__(self):
...         return hash(self.name) ^ hash(self.is_terminal)
...     def __eq__(self, other):
...         print('{} __eq__ {}'.format(self, other))
...         return (self.is_terminal, self.name) == (other.is_terminal, other.name)
...     def __lt__(self, other):
...         print('{} __lt__ {}'.format(self, other))
...         return (self.is_terminal, self.name) < (other.is_terminal, other.name)
...
>>> symbols = set()
>>> for s in "abcdef":
...     symbols.add(Symbol(s))
...
>>> sorted(symbols)
Symbol('f', is_terminal=False) __lt__ Symbol('c', is_terminal=False)
Symbol('a', is_terminal=False) __lt__ Symbol('f', is_terminal=False)
Symbol('a', is_terminal=False) __lt__ Symbol('f', is_terminal=False)
Symbol('a', is_terminal=False) __lt__ Symbol('c', is_terminal=False)
Symbol('b', is_terminal=False) __lt__ Symbol('c', is_terminal=False)
Symbol('b', is_terminal=False) __lt__ Symbol('a', is_terminal=False)
Symbol('d', is_terminal=False) __lt__ Symbol('c', is_terminal=False)
Symbol('d', is_terminal=False) __lt__ Symbol('f', is_terminal=False)
Symbol('e', is_terminal=False) __lt__ Symbol('c', is_terminal=False)
Symbol('e', is_terminal=False) __lt__ Symbol('f', is_terminal=False)
Symbol('e', is_terminal=False) __lt__ Symbol('d', is_terminal=False)
[Symbol('a', is_terminal=False), Symbol('b', is_terminal=False), Symbol('c', is_terminal=False), Symbol('d', is_terminal=False), Symbol('e', is_terminal=False), Symbol('f', is_terminal=False)]

事实上，即使没有 @total_ordering 也可以进行排序，因为 TimSort 实现仅使用 __lt__；这是explicitly document :

This method sorts the list in place, using only < comparisons between items.

排序键也是一个选项，只需从键返回 (is_terminal, name) 元组:

>>> sorted(symbols, key=lambda s: (s.is_terminal, s.name))
[Symbol('a', is_terminal=False), Symbol('b', is_terminal=False), Symbol('c', is_terminal=False), Symbol('d', is_terminal=False), Symbol('e', is_terminal=False), Symbol('f', is_terminal=False)]

请注意，现在永远不会调用 __lt__ 方法，因为使用的是排序键。