La forma más rápida de buscar una lista en Python

Cuando haces algo como "test" in a donde está una lista, ¿python realiza una búsqueda secuencial en la lista o crea una representación de tabla hash para optimizar la búsqueda? En la aplicación, necesito esto para hacer muchas búsquedas en la lista, ¿así que sería mejor hacer algo como b = set(a) y luego "test" in b ? También tenga en cuenta que la lista de valores que tendré no tendrá datos duplicados y realmente no me importa el orden en que se encuentra; Solo necesito poder verificar la existencia de un valor.

También tenga en cuenta que la lista de valores que tendré no tendrá datos duplicados y realmente no me importa el orden en que se encuentra; Solo necesito poder verificar la existencia de un valor.

No uses una lista, usa un set() lugar. Tiene exactamente las propiedades que desea, incluida una prueba rápida in llamas.

He visto incrementos de velocidad de 20x y más en lugares (en su mayoría crujidos de números pesados) donde se cambió una lista para un conjunto.

"test" in a con una lista a hará una búsqueda lineal. Configurar una tabla hash sobre la marcha sería mucho más costoso que una búsqueda lineal. "test" in b por otro lado, hará una búsqueda de hash O (1) amoirtised.

En el caso que describe, no parece haber una razón para usar una lista sobre un conjunto.

Creo que sería mejor ir con la implementación del set. Sé por un hecho que los conjuntos tienen O (1) tiempo de búsqueda. Creo que las listas toman O (n) tiempo de búsqueda. Pero incluso si las listas también son O (1) de búsqueda, no se pierde nada con el cambio a conjuntos.

Además, los conjuntos no permiten valores duplicados. Esto hará que tu progtwig también sea un poco más eficiente en memoria

La lista y las tuplas parecen tener el mismo tiempo, y el uso de “in” es lento para datos grandes:

 >>> t = list(range(0, 1000000)) >>> a=time.time();x = [b in t for b in range(100234,101234)];print(time.time()-a) 1.66235494614 >>> t = tuple(range(0, 1000000)) >>> a=time.time();x = [b in t for b in range(100234,101234)];print(time.time()-a) 1.6594209671 

Aquí hay una solución mucho mejor: la forma más eficiente de buscar / buscar en una lista enorme (python)

Es super rapido

 >>> from bisect import bisect_left >>> t = list(range(0, 1000000)) >>> a=time.time();x = [t[bisect_left(t,b)]==b for b in range(100234,101234)];print(time.time()-a) 0.0054759979248