Las comprobaciones repetidas x in data dentro de un bucle son lentas. data es una lista de 1 millón de elementos. ¿Cómo lo arreglas?
Opciones
- Ordenar la lista una vez para que las comprobaciones vayan más rápido
- Crear un
setuna vez, para que cada comprobación sea O(1) (Opción correcta) - Convertirla en una tupla, que busca más rápido
- Llamar a
data.index(x)en cada comprobación
Respuesta
Convertirla en un set una vez, para que cada comprobación sea O(1) de media
Por qué
x in some_list revisa los elementos uno a uno: O(n). Hacerlo dentro de un bucle de n iteraciones cuesta O(n²), algo enorme con un millón de elementos.
x in some_set usa hashing: O(1) de media.
Convertir una vez cuesta O(n), y después todas las comprobaciones son baratas.
Recuerda
Muchas comprobaciones de pertenencia → usa un set.