检查两个冻结集在Python中是否相等的时间复杂性 [英] Time-complexity of checking if two frozensets are equal in Python

问题描述

在比较两个冻结集时，Python是否会遍历其中一个集合中的元素，还是因为冻结集是可哈希的，所以它会检查冻结集的哈希值?

Couldn't find the details of this anywhere online, when comparing two frozensets does Python iterate through the elements in one of the sets or does it check the hash values of the frozensets since frozensets are hashable?

推荐答案

由于参考文档对此未做任何说明，因此它依赖于实现，因此除了查看该版本的源代码外，没有答案.您正在使用的Python(在CPython发行版的Objects/setobject.c中).查看Python 3.7.0的源代码，答案是也许";-)

Since the reference docs don't say anything about this, it's implementation-dependent, so there is no answer short of looking at the source code for the version of Python you're using (in your CPython distribution's Objects/setobject.c). Looking at the source for Python 3.7.0, the answer is "maybe" ;-)

相等性首先检查冻结集的大小是否相同(len()).如果不相等，则它们不能相等，因此会立即返回False.

Equality first checks whether the frozensets have the same size (len()). If not, they can't be equal, so False is returned at once.

否则将比较如果已经计算出哈希码.如果已经计算出它们，那么如果哈希码不相等，则立即返回False.调用其他逐个元素的代码来检查一个元素是否是另一个元素的子集.

Else the hash codes are compared if they've already been computed. If they have already been computed, then False is returned at once if the hash codes aren't equal. Else element-by-element code is invoked to check whether one is a subset of the other.

冻结集的哈希码并非仅针对哈希集的哈希值进行计算-这可能是一笔无法弥补的费用.因此，必须采取强制措施.一开始，frozenset的主要用例是允许集合的集合，并且在 上下文中，哈希代码将作为将冻结集合添加到包含集合的正常部分进行计算. C级集实现包含一个槽，用于在计算哈希时和计算时记录哈希，并将其初始化为-1(保留值，内部表示未知哈希码").

A hash code for a frozenset isn't computed just for the heck of it - that would be an expense that may not pay off. So something has to force it. The primary use case for frozensets at the start was to allow sets of sets, and in that context hash codes will be computed as a normal part of adding a frozenset to a containing set. The C-level set implementation contains a slot to record the hash if and when it's computed, which is initialized to -1 (a reserved value that means "no hash code known" internally).

这篇关于检查两个冻结集在Python中是否相等的时间复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！