python - 在 Python 中检查两个冻结集是否相等的时间复杂度
问题描述
无法在网上任何地方找到详细信息,当比较两个frozensets 时,Python 是遍历其中一个集合中的元素还是检查frozensets 的哈希值,因为frozensets 是可散列的?
解决方案
由于参考文档对此没有任何说明,它依赖于实现,因此除了查看您正在使用的 Python 版本的源代码(在您的 CPython 发行版中)之外,没有任何答案Objects/setobject.c
。查看 Python 3.7.0 的源代码,答案是“也许”;-)
平等首先检查冻结集是否具有相同的大小 ( len()
)。如果不是,它们不能相等,所以False
立即返回。
否则,如果它们已经被计算,则比较哈希码。如果它们已经被计算过,那么False
如果哈希码不相等,则立即返回。否则调用逐个元素的代码来检查一个是否是另一个的子集。
冻结集的哈希码不仅仅是为了它而计算的——这将是一笔可能无法得到回报的费用。所以必须有东西强迫它。freezesets 一开始的主要用例是允许集合的集合,在这种情况下,哈希码将作为将frozenset 添加到包含集合的正常部分来计算。C-level set 实现包含一个槽来记录哈希是否以及何时计算,它被初始化为 -1(一个保留值,表示内部“没有已知的哈希码”)。
推荐阅读
- r - 将数据帧从一个第一个转换为另一个
- laravel - 为 Eloquent Laravel 5.7 的 whereMonth 订购一天?
- amazon-web-services - 是否可以在没有运行 EC2 实例的情况下运行 Terrafrom/Ansible 脚本?
- cors - CorsHttpHandler 是否支持通配符以允许任何域?
- c - 动态库文件的全局变量加载到哪里?
- twilio - 如何使 VoiceResponse 中 TwiML 重定向的端点命中返回 MessagingResponse?
- python - 如果用户最后这么说,如何让脚本自行重启?
- dijkstra - 有人在 OPL 中使用过 Dijkstra 算法吗?
- ada - 无法在 GNAT 2019 社区版的 microbit 上获得 Ada 滚动文本演示
- java - 删除重复项java(集合)后对alpha进行排序的方法