Python: listas VS conjuntos

Imagen creada con IA

En Python, una de las diferencias fundamentales entre los tipos de datos lista (list) y conjunto (set) es que el segundo no puede tener duplicados. De hecho cuando queremos eliminar los duplicados de una lista, una de las maneras de hacerlo es transformar la lista en conjunto y luego volver a pasar el conjunto a lista.

No entro aquí en el tipo de datos que puede contener cada uno de ellos. Si mi variable debe admitir datos duplicados necesariamente debo utilizar una lista. Pero si hay la certeza de que no habrá ningún dato duplicado (o no queremos almacenarlo más de una vez) podemos elegir entre usar una lista o un conjunto. Lo cierto es que la versatilidad de las listas hace que muchas veces nos decantemos por estas, pero no siempre es la mejor opción como mostraré a continuación.

Cuando la cantidad de datos con los que voy a trabajar es considerable, los tiempos de ejecución de los programas puede variar muy significativamente si utilizo listas o si utilizo conjuntos (cuando pueda hacerlo).

¿Hay diferencia en tiempo de ejecución al recorrer una lista y al recorrer un conjunto, ambos con los mismos elementos?

Imagen creada con IA

He hecho una prueba en el ordenador en el que me encuentro escribiendo esta entrada. He creado una lista y un conjunto con los números del 0 al 100000000, este último sin incluir. Recorriendo ambos con un bucle "for ... in" he obtenido los siguientes tiempo de ejecución:

    Tiempo de recorrido en lista: 5.245566 segundos

    Tiempo de recorrido en conjunto: 5.883574 segundos

El tiempo de recorrido sobre el conjunto es aproximadamente un 12% superior al tiempo de recorrido sobre la lista.

Además, en el mismo programa he buscado el elemento 99999999 en la lista (if ... in) y los tiempos de ejecución han sido los siguientes:

    Tiempo de búsqueda en lista: 1.093401 segundos

    Tiempo de búsqueda en conjunto: 0.000001 segundos

El tiempo de búsqueda en el conjunto es muchísimo más corto que el tiempo de búsqueda en la lista y aunque no busquemos el último elemento los tiempos siguen siendo significativamente muy inferiores. Esto en programas con gran cantidad de datos o que debemos realizar muchas búsquedas en una colección de datos puede suponer la diferencia entre un programa con un tiempo de ejecución aceptable o uno de esos que dejas el ordenador encendido y al cabo de muchas horas vuelves para mirar si con suerte ya ha acabado (a mi me pasó con el problema de los cartones del bingo).

A continuación incluyo el código del programa utilizado:

import time

n = 100000000

elementos = list(range(n))

elementoZ = n-1

mi_lista = elementos

mi_conjunto = set(elementos)

# Medir tiempo de recorrido en lista

inicio = time.time()

for elemento in mi_lista:

next

tiempo_lista = time.time() - inicio

# Medir tiempo de recorrido en conjunto

inicio = time.time()

for elemento in mi_conjunto:

next

tiempo_conjunto = time.time() - inicio

print(f"Tiempo de recorrido en lista: {tiempo_lista:.6f} segundos")

print(f"Tiempo de recorrido en conjunto: {tiempo_conjunto:.6f} segundos")

# Medir tiempo de búsqueda en lista

inicio = time.time()

if elementoZ in mi_lista:

tiempo_lista = time.time() - inicio

# Medir tiempo de búsqueda en conjunto

inicio = time.time()

if elementoZ in mi_conjunto:

tiempo_conjunto = time.time() - inicio

print(f"Tiempo de búsqueda en lista: {tiempo_lista:.6f} segundos")

print(f"Tiempo de búsqueda en conjunto: {tiempo_conjunto:.6f} segundos")

Referencia externa sobre el tema: en la documentación de Python, apartado TimeComplexity, se muestra que de promedio una búsqueda "in" en listas tiene orden O(n) y en conjuntos O(1).