Python的'in'或'not in'运算符效率如何？

Question

我有一个超过100000个值的列表,我正在迭代这些值并检查每个值是否包含在另一个随机值列表中(相同大小).

我这样做是通过使用if item[x] in randomList.这有多高效？python是否为每个容器进行某种散列,或者它是否在内部直接搜索另一个容器以找到我正在寻找的元素？

此外,如果它线性搜索,那么它是否会创建randomList的字典并使用它进行查找？

Answer 1

in是通过__contains__它所适用的对象的魔术方法实现的,因此效率取决于此.例如,set,dict并frozenset会基于散列的查找,同时list需要一个线性搜索.但是,xrange(或range在Python 3.x中)有一种__contains__方法不需要线性搜索,而是可以使用开始/停止/步骤信息来确定真值.(例如:7 in xrange(4, 1000000)不是线性完成的).

自定义类可以自由实现,__contains__但是他们认为合适但理想情况下应该提供一些有关如何在文档中执行此操作的信息(如果"不明显").