python - 如何在 Python 中实现frozenset 相等？

Question

CPython 中如何实现frozenset 相等？特别是，我想知道 frozenset 中的各个元素如何相互比较以及它们的总时间复杂度。

我查看了set 和 freezeset 在实现和https://stackoverflow.com/a/51778365/5792721中的差异。

第二个链接中的答案涵盖了比较集合中各个元素之前的步骤，但缺少实际的比较算法。

Answer 1

有问题的实现可以在这里找到。sets v假设我们要检查两个和w是否相等，该算法是这样的：

1. 检查它们的大小是否相等。如果不是，则返回false。

这引用了 的size属性PySetObject，因此它是一个常数时间操作。

2. 检查两者sets是否都是frozensets. 如果是这样，并且它们的哈希值不同，则返回false。

同样，这引用了 的hash属性PySetObject，这是一个常数时间操作。这是可能的，因为frozensets它们是不可变的对象，因此在创建它们时会计算它们的哈希值。

3. 检查是否w是 的子集v。

这是通过遍历 的每个元素v并检查它是否存在于 中来完成的w。

迭代必须在所有 上执行v，因此在最坏的情况下它的大小是线性的（如果在最后一个位置找到不同的元素）。

成员资格测试sets通常在平均情况下需要恒定时间，在最坏情况下需要线性时间；将两者结合起来，在平均情况下与时间的大小呈线性关系，在最坏情况v下与时间成正比。len(v) * len(w)

从某种意义上说，这是最坏情况的平均情况，因为它假设前两次检查总是返回true。如果您的数据很少倾向于具有相同大小sets且具有相同哈希但包含不同对象的数据，那么在平均情况下，比较仍将在恒定时间内运行。

Answer 2

set和freezeset都使用该set_richcompare()函数进行相等性测试。这里没有区别。

set_richcompare()，正如其他答案所提到的，比较大小然后散列。然后，它检查一个是否是另一个的子集，它只是遍历集合 1 中的每个元素，并检查它是否在集合 2 中。此检查在其他方面与检查元素是否在集合中相同。这是通过哈希表查找来完成的，对具有相同哈希值的项目进行线性搜索。存在性检查的复杂性是O(1) 摊销或 O(len(s)) 最坏情况，因此检查set_issubset()的复杂性是 O(len(s1)) 摊销或 O(len(s1)*len (s2)) 最坏情况。