__eq__() 在嵌套数据结构中多次调用而不是一次

Question

一年一两次，我遇到以下问题：我有一些比较操作可能很昂贵的类型（例如，值太大而无法保存在内存中，需要从磁盘加载或相等性很难计算，因为单个值可能有多种表示，想想化学式）。这种类型是嵌套数据结构的一部分（例如嵌套列表或元组或某些树）。有时我注意到比较运算符 (__lt__我的类型上等）对于单个比较的相同值被多次调用。

我将尝试用以下示例来说明问题：

class X:
    comparisons = 0

    def __init__(self, value):
        self.value = value

    def __lt__(self, other):
        return self.value < other.value

    def __gt__(self, other):
        return self.value > other.value

    def __eq__(self, other):
        X.comparisons += 1
        return self.value == other.value

def nest_a_hundred_times(value):
    for i in range(100): value = [value]
    return value

print(nest_a_hundred_times(X(1)) < nest_a_hundred_times(X(0)))
print(X.comparisons)

在这个例子中，X是我的类型具有昂贵的比较操作，我只是计算次数__eq__()被调用但其他操作也可能很昂贵。该类型的两个不相等的值被创建并嵌套在单元素列表中多次。

运行示例打印False, 100。所以__eq__()被调用了100次。

我知道为什么发生这种情况：对于内置比较函数list对象平等单个列表元素首先比较，发现在该指数两个列表不同，比较订货那些元素之前。我认为当仅使用六个比较运算符（==, !=, <, <=, >, >=）作为定义排序的类型之间的接口时，实际上无法避免这个问题。作为替代方法的一个例子，Haskell 有一个Ord类，它定义了一个ordering函数来比较两个值。这允许通过ordering在每个节点上仅调用一次来比较嵌套数据结构。

我的问题是：如何在 Python 中避免这个问题？与我的信念相反，是否有可能避免仅由 Python 定义的比较运算符的问题？（我试图避免某种结果缓存，因为这不是性能问题，而是算法问题）。或者我是否需要构建自己的数据结构（列表、元组）并ordering在它们上实现一个函数？

Answer 1

从你提出问题的方式来看，我假设：

• 如果可能的话，您不希望覆盖list.__eq__。（我也不想，这是一个非常危险的想法）。
• 如果需要，您可以覆盖 dunder( __) 方法X。（据我所知这是必要的）。

正如您所暗示的那样，因为您正在尝试解决内置类型上内置操作的实现，所以我认为任何解决方案都不会特别干净（但嘿也许其他答案会让我感到惊讶）。

我发现一个有趣的事情是，如果你覆盖X.__eq__return True，它只会被调用一次。

class X:
    ...
    def __eq__(self, other):
        X.comparisons += 1
        return True

现在显然这可能会产生一些问题，因为它会导致X(1)==X(0)和nest_a_hundred_times(X(1)) == nest_a_hundred_times(X(0))。然而，它会使工作更加高效，所以如果你确信你永远不需要使用 ==，我认为这可能是一种方法<。>

除此之外，我所能想到的就是一个公认的混乱的黑客尝试检测是否__eq__被调用<或“>”或被==......

import inspect

class X:
    ...
    def __eq__(self, other):
        X.comparisons += 1
        f = inspect.currentframe().f_back
        fi = inspect.getframeinfo(f)
        line_called_from = fi[-2][0]
        called_from_lt = ('<' in line_called_from  or '>' in line_called_from) and '==' not in line_called_from and 'eq(' not in line_called_from
        if called_from_lt:
            return True
        return self.value == other.value