python 的 `in` 函数在通过 `getitem()`' 触发时如何工作？

Question

The official documentation 表示 python 首先尝试通过 __contains__() 进行检查，然后是 __iter__()，最后是 __getitem__()，具体取决于定义的函数，为了解决 in 呼叫。例如：

if y in x:
    print("y present in x")
else:
    print("y not present in x")

链接的文档指出，如果存在任何非负索引 i 使得 x[i] == y，则结果为 True 否则 False。它如何对所有这些 i 执行搜索？对 'all' 正数的线性遍历似乎是不可能的。线性遍历必须有一些界限（对于列表，它应该是 0 到 len()）。这些界限是如何确定的？

Answer 1

这正是它的工作原理。这是使用 list:

的演示

$ for a in `seq 6`; do python3 -m timeit -s "a = 10**$a" 'a in list(range(a))'; done
1000000 loops, best of 3: 0.84 usec per loop
100000 loops, best of 3: 3.04 usec per loop
10000 loops, best of 3: 57.7 usec per loop
1000 loops, best of 3: 639 usec per loop
100 loops, best of 3: 6.74 msec per loop
10 loops, best of 3: 70.3 msec per loop

您可以观察到时间复杂度与容器的大小成正比。

Answer 2

How does it perform a search over all such i?

这在很大程度上取决于执行搜索的对象的数据结构。例如，如果您有一个 list 对象，则成员资格检查的复杂度为 O(n)，并且如果您有一个使用散列 table 访问其项目的数据结构（__getitem__ 属性）比如字典或者集合复杂度大约是O(1).

因此，一般来说，对于用户定义的对象，它的工作原理与文档中的解释相同。对于没有散列 table 的对象，它是线性搜索，对于具有散列 table 的对象，它是持续搜索。

Answer 3

这些特殊方法的目的是为您的数据结构设计者您提供一种适合您的情况的快速执行查找的方法。例如，您可以从 list 派生一个 class，它通过反向索引得到增强，以便按值快速查找。（显然这会减慢插入速度，因为需要更新索引，但我们假设您将进行大量查找，因此您知道这是值得的。）

如果您的 class 无法改进默认访问，则无需定义特殊方法。 Python 将返回任何可用的内容，包括顺序搜索。

Answer 4

啊啊啊，我想明白了...您想知道如何获取 key 以遍历自定义容器上既没有 __contains__() 的所有元素] 也不是 __iter__() - 简单，它使用线性迭代精确工作，直到遇到 IndexError，如文档中所述：

... if a class defines __getitem__(), x in y is True if and only if there is a non-negative integer index i such that x == y[i], and all lower integer indices do not raise IndexError exception. (If any other exception is raised, it is as if in raised that exception).

例证：

class CustomClass(object):

    def __getitem__(self, item):
        if item > 20:  # lets force the break so that it doesn't go to sys.maxsize
            raise IndexError()
        print(item)  # print the item requested
        # implied: return None so it doesn't match 5

result = 5 in CustomClass()  # this will keep printing numbers until 20

Answer 5

没有 __contains__ 或 __iter__ 的对象的迭代发生 here. The sequence scan occurs here. The decision to use __contains__ or falling back on iteration occurs here。

python 的 `in` 函数在通过 `getitem()`' 触发时如何工作？

How does python's `in` function work when it triggers via `getitem()`'?

python

membership

python 的 `in` 函数在通过 `__getitem__()`' 触发时如何工作？

How does python's `in` function work when it triggers via `__getitem__()`'?

python

membership

python 的 `in` 函数在通过 `getitem()`' 触发时如何工作？

How does python's `in` function work when it triggers via `getitem()`'?