Python的“输入"效率/速度如何? (时间复杂度明智) [英] How efficient/fast is Python's 'in'? (Time Complexity wise)

问题描述

在Python中，in关键字的效率是多少，例如:

In Python, what is the efficiency of the in keyword, such as in:

a = [1, 2, 3]
if 4 in a:
  ...

推荐答案

这取决于右手

运算符in和not in测试集合成员身份. [...]收集成员资格测试传统上是绑定到序列上的；如果该对象是一个序列，并且包含与该对象相等的元素，则该对象是该集合的成员.但是，对于许多其他对象类型来说，无需顺序即可支持成员资格测试是有意义的.尤其是，字典(用于键)和集合支持成员资格测试.

The operators in and not in test for collection membership. [...] The collection membership test has traditionally been bound to sequences; an object is a member of a collection if the collection is a sequence and contains an element equal to that object. However, it make sense for many other object types to support membership tests without being a sequence. In particular, dictionaries (for keys) and sets support membership testing.

类可以实现特殊方法__contains__ 来覆盖默认行为(遍历序列)，因此与比较容器的每个元素相比，可以提供一种(或更少)有效的方式来测试成员资格.

Classes can implement the special method __contains__ to override the default behavior (iterating over the sequence) and thus can provide a more (or less) efficient way to test membership than comparing every element of the container.

成员资格测试运算符(in和not in)通常实现为序列的迭代.但是，容器对象可以为以下特殊方法提供更有效的实现，这也不需要对象成为序列.

The membership test operators (in and not in) are normally implemented as an iteration through a sequence. However, container objects can supply the following special method with a more efficient implementation, which also does not require the object be a sequence.

---

由于示例中有一个列表，因此对其进行迭代，并比较每个元素，直到找到匹配项或列表用尽.时间复杂度通常为O(n).

这篇关于Python的“输入"效率/速度如何? (时间复杂度明智)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！