当你调用`if key in dict`时会发生什么 [英] What happens when you call `if key in dict`
问题描述
我有一个类(我们称之为 myClass
)实现 __哈希__
和 __eq __
。我还有一个 dict
将 myClass
对象映射到某种值,计算需要一些时间。
在我的程序中,许多(数百万的数量级) myClass
对象被实例化。这就是为什么我使用 dict
跟踪这些值。
然而,有时候新的 myClass
对象可能等同于较旧的(由 __ eq __
方法定义)。因此,不要再次计算该对象的值,我宁愿只在 dict $ c $中查找旧的
中,那么我做 myClass
对象的值C>。为了达到这个目的,如果在dict中的myNewMyClassObj在。
这是我的问题:
当我在子句中使用时,调用什么,
中的myNewMyClassObj? __ hash __
或 __当量__
?使用 dict
的观点是它是O(1)查找时间。所以必须调用 __ hash __
。但是如果 __ hash __
和 __ eq __
不是等效的方法呢?在这种情况下,如果在
跟进问题: p>
我想最小化我的 dict
中的条目数量,所以我最好只保留一个集合在 dict
中的等价物 myClass
对象。所以再一次,似乎在计算时需要调用
,那么这将污染一个 __ eq __
,如果dict中的myNewClassObj dict
的O(1)查找时间到O(n)查找时间
首先,调用 __ hash __(myNewMyClassObj)
。如果没有在字典中找到具有相同散列的对象,则Python假定 myNewMyClassObj
不在字典中。 (请注意,Python要求每当 __ eq __
评估为两个对象相等时,它们的 __ hash __
必须相同。 p>
如果在字典中找到一些具有相同 __ hash __
的对象, __ eq __
每个都被调用。如果 __ eq __
评估为任何一个相等,则dict _ 中的 myNewMyClassObj将返回True。
因此,您只需要确保 __ eq __
和 __哈希__
都很快。
对于您的跟进问题:是的, dict _
仅存储一组等效的 MyClass
对象(由 __ eq __
定义)。 (正如设置)
请注意,只有具有相同哈希值的对象才调用 __ eq __
分配到同一个桶。这样的对象的数量通常是非常小的数字( dict
实现确保)。所以你还有(大概) O(1)
查询性能。
I have a class (let's call it myClass
) that implements both __hash__
and __eq__
. I also have a dict
that maps myClass
objects to some value, computing which takes some time.
Over the course of my program, many (in the order of millions) myClass
objects are instantiated. This is why I use the dict
to keep track of those values.
However, sometimes a new myClass
object might be equivalent to an older one (as defined by the __eq__
method). So rather than compute the value for that object again, I'd rather just lookup the value of older myClass
object in the dict
. To accomplish this, I do if myNewMyClassObj in dict
.
Here's my question:
When I use that in
clause, what gets called, __hash__
or __eq__
? The point of using a dict
is that it's O(1) lookup time. So then __hash__
must be called. But what if __hash__
and __eq__
aren't equivalent methods? In that case, will I get a false positive for if myNewMyClassObj in dict
?
Follow up question:
I want to minimize the number of entries in my dict
, so I would ideally like to keep only one of a set of equivalent myClass
objects in the dict
. So again, it seems that __eq__
needs to be called when computing if myNewClassObj in dict
, which would defile a dict
's O(1) lookup time to an O(n) lookup time
First, __hash__(myNewMyClassObj)
gets called. If no object with the same hash is found in the dictionary, Python assumes myNewMyClassObj
is not in the dictionary. (Note that Python requires that whenever __eq__
evaluates as equal for two objects, their __hash__
must be identical.)
If some objects with the same __hash__
are found in the dictionary, __eq__
gets called on each of them. If __eq__
evaluates as equal for any of them, the myNewMyClassObj in dict_
returns True.
Thus, you just need to make sure both __eq__
and __hash__
are fast.
To your follow up question: yes, dict_
stores only one of a set of equivalent MyClass
objects (as defined by __eq__
). (As does set.)
Note that __eq__
is only called on the objects that had the same hash and got allocated to the same bucket. The number of such objects is usually a very small number (dict
implementation makes sure of that). So you still have (roughly) O(1)
lookup performance.
这篇关于当你调用`if key in dict`时会发生什么的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!