¿Qué tan eficiente / rápido es Python’s ‘in’? (Complejidad del tiempo sabio)

En Python, ¿cuál es la eficiencia de la palabra clave, como en:

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

Related of "¿Qué tan eficiente / rápido es Python’s ‘in’? (Complejidad del tiempo sabio)"

Depende del operando de la mano derecha:

Los operadores in y not in prueba para la membresía de colección. […] La prueba de pertenencia a la colección ha sido tradicionalmente vinculada a secuencias; un objeto es miembro de una colección si la colección es una secuencia y contiene un elemento igual a ese objeto. Sin embargo, tiene sentido que muchos otros tipos de objetos admitan las pruebas de pertenencia sin ser una secuencia. En particular, los diccionarios (para claves) y los conjuntos de pruebas de compatibilidad de soporte

Las clases pueden implementar el método especial __contains__ para anular el comportamiento predeterminado (iterar sobre la secuencia) y, por lo tanto, puede proporcionar una manera más (o menos) eficiente de probar la membresía que comparar cada elemento del contenedor.

Los operadores de prueba de membresía ( in y not in ) normalmente se implementan como una iteración a través de una secuencia. Sin embargo, los objetos contenedores pueden proporcionar el siguiente método especial con una implementación más eficiente, que tampoco requiere que el objeto sea una secuencia.


Como tiene una lista en su ejemplo, se repite y se compara cada elemento hasta que se encuentra una coincidencia o se agota la lista. La complejidad del tiempo suele ser O(n) .

La complejidad de las listas es:

 O(n) 

Para conjuntos es:

 O(1) 

http://wiki.python.org/moin/TimeComplexity