tamaño - La forma más rápida de buscar una lista en python

recorrer lista python

Question

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.

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 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 aceleraciones de 20x y más en lugares (en su mayoría, crujidos de números pesados) donde se cambió una lista por conjunto.

Answer 2

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 al cambiar a conjuntos.

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

Answer 3

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

Answer 4

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