23

I am working in python and I have some problem with heapq. When I push an element into the heap I receive this error :

TypeError: '<' not supported between instances of 'Point' and 'Point'

Point is my internal class. I push a tuple formed by (float,Point), in according with documentation, heapq should use float as a key, but it doesn't. To be more precise sometimes use float but not always. What is the problem?

4

2 回答 2

31

heapq将<=在您放入其中的任何内容上使用运算符。

元组逐个位置进行比较：第一个元组的第一项与第二个元组的第一项进行比较；如果它们不相等（即第一个大于或小于第二个），则这是比较的结果，否则考虑第二个项目，然后考虑第三个，依此类推。

如果每个元组的第一项是唯一的，则比较总是只在第一项上发生：

>>> x = (1, object())
>>> y = (2, object())
>>> x <= y
True

（注意：我object()以前创建了一个匿名对象，它没有实现比较运算符）

当元组的第一项不唯一时出现问题（即第一个元组项对于某些元组将相等），那么比较将不得不比较元组的第二项：

>>> z = (1, object())
>>> x <= z
Traceback (most recent call last):
  File "<input>", line 1, in <module>
    x <= z
TypeError: '<=' not supported between instances of 'object' and 'object'

因此，您可以在对象中实现比较运算符：

  • __lt__(self, other)对于<
  • __le__(self, other)对于<=
  • （可选）__gt__(self, other)对于>
  • （可选）__ge__(self, other)对于>=

否则，您要确保元组中的前面的项目始终是可比较的并且一起是唯一的。

例如，您可以将对象的 id 添加到元组中，以便您的元组变为：

(priority, id(obj), obj)

因为对象 id 是唯一的。（请注意：如果添加具有相同优先级的同一对象的两个实例，您将再次遇到此问题）。

于 2018-11-30T09:19:50.577 回答
7

您需要在Point类中定义相对比较操作。这表示：

__lt__(self, other)为了<

__le__(self,other)为了<=

并且可选

__gt__(self, other)为了>

__ge__(self, other)为>=.

最后两个是可选的，因为如果未指定，则取le和lt取反。

这些方法的一般结构是__name__(self, other)，where otheris object which will be compare to self。此外，他们返回Trueor False。

您也可以定义__eq__而不是上面的所有四个，它的工作方式类似于 Java 中的比较器。self如果大于，则此方法应返回正整数，如果other它们相等则返回 0，如果大于 则返回负other整数self。

于 2018-11-30T09:00:52.400 回答