我目前正在学习一门基础的计算机科学课程,我们经常使用Python的in
方法。我很好奇这个方法是如何实现的,它背后的代码是什么样子的。
我可以想象出我自己实现这个方法的方式,但是在提交了几份作业之后,我发现我的做法通常很糟糕和低效。因此,我想开始调查“好”的代码。
我目前正在学习一门基础的计算机科学课程,我们经常使用Python的in
方法。我很好奇这个方法是如何实现的,它背后的代码是什么样子的。
我可以想象出我自己实现这个方法的方式,但是在提交了几份作业之后,我发现我的做法通常很糟糕和低效。因此,我想开始调查“好”的代码。
in
的实现是分散的--每种类型都有一个实现,以及一个更一般的实现调用特定于类型的实现(稍后详细说明)。例如,对于列表,我们将寻找列表的实现。在Python源代码树中,所有内置对象的源代码都在Objects目录中。在那个目录中,您会找到listobject.c,其中包含了列表对象及其所有方法的实现。__contains__
方法,这解释了函数的名称)。它相当简单,只需循环遍历列表的所有元素,直到找到元素或没有更多元素,并返回搜索结果。 :)def __contains__(self, obj):
for item in self:
if item == obj:
return True
return False
abstract.c
中的PySequence_Contains
的实现中看到。它尝试调用特定于类型的版本,如果失败,则转而进行常规迭代。那个循环是在使用Python C-API将常规Python for循环编写为C时的样子。从Python语言参考手册的数据模型部分:
成员测试运算符(
in
和not in
)通常是通过对序列进行迭代来实现的。然而,容器对象可以提供以下特殊方法,以更有效的实现,也不需要对象是一个序列。
object.__contains__(self, item)
调用以实现成员测试运算符。如果item在self中,则应返回true,否则返回false。对于映射对象,这应该考虑映射的键而不是值或键-项对。
对于未定义
__contains__()
的对象,成员测试首先尝试通过__iter__()
进行迭代,然后尝试旧的序列迭代协议通过__getitem__()
,请参阅语言参考中的此部分。
因此,默认情况下,Python迭代序列以实现in
运算符。如果一个对象定义了__contains__
方法,Python会使用它来替代迭代。那么在__contains__
方法中会发生什么?要确切地知道,您需要浏览源代码。但我可以告诉您,Python的列表使用迭代实现__contains__
。Python字典和集合是作为哈希表实现的,因此支持更快的成员测试。
in
运算符在字符串对象中调用__contains__
方法 - 因此您可以检查两个项目中字符串的实现 - 但实际搜索代码将被深埋。http://hg.python.org/cpython/file/c310233b1d64/Objects/stringlib/fastsearch.h
in
有自己的字节码指令,应该猜到他们会重用 C-API 实现的代码。 - user395760