python - Python如何确定两个集合是否相等？有什么可能的优化吗？

Question

我知道如果我们只做简单的迭代，实现集合相等很容易

def __eq__(self, b):
    if len(self) != len(b): # Cut fast optimization
        return False
    for x in self:
        if x not in b:
            return False
    for x in b:
        if x not in a:
            return False
    return True

有没有更有效的方法来实现这一点？对于这些相等性，Python 是否执行了任何优化(或可能对计算非冲突哈希进行优化)？

Answer 1

CPython的实现
集合相等的内置优化取决于正在使用的 Python 的实现，在大多数情况下是 CPython。您可以查看the internal definition of set objects和 how set comparisons are implemented通过查看 CPython 的源代码。
首先，重要的是要注意 Python 具有类 Set和 FrozenSet .主要区别在于 FrozenSet 的实例是不可变的，因此是可散列的，可以用作散列键；仅针对 FrozenSet 的实例计算散列成员(见 struct definition)。它们在 CPython 中很大程度上共享相同的代码库。 CPython 使用以下步骤来确定集合相等性:

比较集合的大小

比较集合的哈希值(仅 FrozenSet!)

集合 v 是 w 的子集吗？

哈希可能会发生冲突，因此为什么在比较 FrozenSet 的实例时仍然需要其他步骤.
CPython 的优化
一个典型的基线实现会检查这两个集合是否是彼此的子集。您的示例还通过比较集合的大小来确定集合不等式，从而实现了非常直观的优化。
CPython 实现了 Arya McCarthy 和 Tim Peters 已经指出的优化:比较大小(步骤 1)并检查一个集合是否是另一个集合的子集(步骤 3)足以确定相等性。这将确定集合相等性所需的时间减少了一半。
CPython 还为 FrozenSet 的实例实现了另一种优化。通过比较它们的哈希值，但这些值可能会发生冲突。因此，我们只能依靠不匹配的值作为两个集合不相等的指标，代价是 O(1)。然而，匹配的哈希值并不意味着两个集合是相等的，因为冲突是可能的。
我不知道(重新)计算可变集的哈希值引入的额外开销是否值得，但也许 CPython 的实现可以受益于仅在需要时在内部计算/使用哈希值以确定相等性的解决方案。这就是可变泛型集可能从基于散列的优化中受益的地方。
非冲突哈希
您提到了一种基于非冲突哈希的优化策略，但据我所知，非冲突哈希和泛型集不能一起使用，无论实现如何。
( Here's a link to a post on crypto.stackexchange.com that explains the problem pretty well.)
如果集合可以使用非冲突哈希，那么确定两个集合是否相等所需的唯一步骤就是比较两个集合的哈希值。这将是一个大规模的优化，因为它将在所有情况下将确定集合相等的成本降低到 O(1)。不再需要 CPython 实现的第 1 步和第 3 步。
话虽如此，对于特定的问题域，仍然可以使用非冲突的哈希值，其中集合的内容以某种方式受到限制，因此存在一个保证哈希值不会发生冲突的哈希函数。 在这种情况下，您可能不应该依赖 Python 的内置集合，或者在 Python 中实现您自己的专用集合(以避免所有额外的开销)。相反，您最好的选择是在 C/C++ 中实现您自己的一组专用实现，并使用 Python 绑定(bind)将您的专用实现集成到 Python 中。