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

Question

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

我看了一下set and frozenset difference in implementation和 https://stackoverflow.com/a/51778365/5792721 .

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

Answer 1

可以找到有问题的实现 here .假设我们要检查两个 set v 和 w 是否相等，该算法是这样的:

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

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

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

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

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

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

迭代必须在整个 v 上执行，因此在最坏的情况下它的大小是线性的(如果在最后一个位置发现不同的元素)。

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

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