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.La forma más rápida de buscar una lista en python
Respuesta
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.
"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.
Esto solo es cierto si hay muchas búsquedas realizadas en b después de su construcción. Si b necesita (re) construirse cada vez que se realiza una búsqueda, entonces '" prueba "en b' será más lenta, ya que la construcción del conjunto no sería lineal. –
@Jamie: Desde el OP: "En la aplicación lo necesito porque haré muchas búsquedas en la lista [...]". Parece que hay muchas búsquedas. –
Estoy de acuerdo en que es la solución correcta, simplemente tratando de dejarlo en claro. –
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í
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
La lista debe ser ordenada primero. –
- 1. La forma más rápida de unificar una lista en Python
- 2. La forma más rápida de reposicionar la sublista en python
- 3. ¿Cuál es la forma más rápida de buscar una lista <T> en varias propiedades?
- 4. ¿Cuál es una forma más rápida de buscar un valor en una lista de tuplas?
- 5. La forma más rápida de empaquetar una lista de flotantes en bytes en python
- 6. La forma más rápida de ordenar en Python
- 7. ¿Cuál es la forma más rápida de buscar una lista larga de palabras para un partido en actionscript 3?
- 8. ¿La forma más rápida de escribir archivos hdf5 con Python?
- 9. En Python, la forma más rápida de crear una lista de archivos en un directorio con una cierta extensión
- 10. Forma más rápida de eliminar duplicados en listas Python
- 11. ¿La forma más eficiente de calcular la frecuencia de valores en una lista de Python?
- 12. ¿La forma más rápida de encontrar un artículo en la lista?
- 13. Psycopg2, Postgresql, Python: la forma más rápida de insertar de forma masiva
- 14. reforma de datos (una forma más rápida)
- 15. ¿La forma más rápida de copiar una tabla en mysql?
- 16. ¿Existe una forma rápida de buscar variables en R?
- 17. La forma más rápida de obtener el último elemento de una lista en Haskell
- 18. ¿Forma más rápida de obtener múltiples FileInfo?
- 19. La forma más rápida de aprender Maven
- 20. La forma más rápida de completar ArrayList
- 21. La forma más rápida de convertir un iterador en una lista
- 22. ¿Cuál es la forma más rápida de revertir una lista separada por comas en vim?
- 23. La forma más rápida de buscar varias páginas web en Java
- 24. ¿Cuál es la forma más rápida de buscar cadenas en Objective-C?
- 25. ¿La forma más rápida y eficiente de buscar un par clave-valor en Java?
- 26. IndexOf demasiado lento en la lista. Una solución más rápida?
- 27. La forma más rápida de tomar una captura de pantalla con Python en Windows
- 28. La forma más rápida de hacer una resta de colección
- 29. ¿La forma más rápida de compilar una aplicación Symbian simple?
- 30. ¿Forma más rápida de sumar una lista de números que con un bucle for?
@blcArmadillo: 'set de son el camino a seguir, ya que no tiene datos duplicados y no se preocupan por fin - además de que siempre se puede enumeración a los miembros del conjunto o rápidamente conviértalo en una lista si es necesario. – martineau
Lo usé y se gasta muchísimo. Gracias. –
Guau, tuve una estúpida escritura bruta forzando a través de dos archivos para encontrar líneas similares, y esto simplemente redujo el tiempo de ~ 20 min a menos de 1. ¡Gracias! – Parker