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

Question

Cuando hace algo como "test" in a donde a es una lista, ¿hace python una búsqueda secuencial en la lista o crea una representación de tabla hash para optimizar la búsqueda? En la aplicación lo necesito porque haré muchas búsquedas en la lista, ¿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.

Answer 1

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 está; Solo necesito poder verificar la existencia de un valor.

No utilice una lista, use un set() en su lugar. Tiene exactamente las propiedades que desea, incluida una prueba in extremadamente rápida.

He visto aceleraciones de 20x y superiores en algunos lugares (la mayoría de los crujidos numéricos) en los que se cambió una lista para un conjunto.

Answer 2

"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) amortizada.

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

Answer 3

Creo que sería mejor ir con la implementación del conjunto. Sé con certeza 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 de búsqueda O (1), no pierde nada al cambiar a conjuntos.

Además, los juegos no permiten valores duplicados. Esto hará que su programa un poco más eficiente de la memoria, así

Answer 4

Lista y tuplas parece tener el mismo tiempo, y el uso de "en" es lento para grandes datos:

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

Aquí es mucho mejor solución: Most efficient way for a lookup/search in a huge list (python)

Es súper rápido:

>>> 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,1)];print(time.time()-a) 
0.0054759979248