python - Python 中如何实现卡住集相等？

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

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

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

最佳答案

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

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

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

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

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

检查 w 是否是 v 的子集。

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

迭代必须在所有 v 上执行，因此在其大小上是最差的线性(如果在最后一个位置找到不同的元素)。
sets 的成员测试通常在平均情况下需要恒定时间，在最坏情况下需要线性时间；将两者结合起来，在平均情况下，时间与 v 的大小成线性关系，而在最坏情况下，时间与 len(v) * len(w) 成正比。

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

关于python - Python 中如何实现卡住集相等？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/56520219/