Dando un paso atrás, puede parecer que la fácil eliminación de duplicados es el único beneficio de usar conjuntos. Ya hemos explicado que los conjuntos no tienen orden; Las matrices tienen un elemento indexado que simplemente podría ignorarse y tratarse como un conjunto. Parece que las matrices pueden hacer el mismo trabajo que un conjunto, si no más.
Sin embargo, esta simplificación impuesta por los conjuntos abre el camino a diferentes implementaciones subyacentes. En las listas, a los elementos se les asignan índices para darle a cada elemento un lugar en el orden. Los conjuntos no necesitan asignar índices, por lo que implementan un enfoque diferente para la referencia: mapeo hash. Estos funcionan asignando aleatoriamente (pseudo) direcciones a elementos, en lugar de almacenarlos en una fila. La asignación se rige por funciones hash, que utilizan el elemento como entrada para generar una dirección.
H(x) es determinista, por lo que la misma entrada siempre da la misma salida, es decir, no hay RNG en la función H, por lo que H(4) = 6 siempre en este caso.
La ejecución de esta función lleva el mismo tiempo independientemente del tamaño del conjunto, es decir. el hash tiene complejidad temporal O(1). Esto significa que el tiempo necesario para el hash es independiente del tamaño de la lista y se mantiene a una velocidad rápida y constante.
Debido a que el hash suele ser rápido, muchas operaciones normalmente lentas en matrices grandes se pueden realizar de manera muy eficiente en un conjunto.
Investigación o pruebas de adherencia
Encontrar elementos en una matriz utiliza un algoritmo llamado búsqueda linealpor marque cada elemento de la lista uno por uno. En el peor de los casos, cuando el elemento buscado no existe en la lista, el algoritmo pasa por cada elemento de la lista (Seguro)). En una lista muy grande, este proceso lleva mucho tiempo.
Sin embargo, dado que el hash es O(1), Python aplica el hash al elemento que se va a encontrar y devuelve su ubicación en la memoria o su inexistencia en un tiempo muy corto.
number_list = range(random.randint(1,000,000))
number_set = set(number_list)#Line 1
#BEGIN TIMER
print(-1 in number_list)
#END TIMER
#Line 2
#BEGIN TIMER
print(-1 in number_set)
#END TIMER
Nota: La búsqueda utilizando un mapa hash tiene un acolchado complejidad temporal de O (1). Esto significa que, en el caso medio, la búsqueda se ejecuta en un tiempo constante, pero técnicamente, en el peor de los casos, la búsqueda es O(n). Sin embargo, esto es extremadamente improbable y se reduce al hecho de que la implementación del hash corre el riesgo de colisión, es decir, cuando varios elementos de una tabla/conjunto hash se envían a la misma dirección.
Borradura
Eliminar un elemento de una lista implica primero buscar para localizar el elemento y luego eliminar la referencia al elemento borrando la dirección. En una matriz, después de una búsqueda de tiempo O (n), el índice de cada elemento que sigue al elemento eliminado debe desplazarse en un punto. Esto en sí mismo es otro proceso O(n).
Eliminar un elemento de un conjunto implica buscar O(1) y luego borrar la dirección de memoria, que es un proceso O(1), por lo que la eliminación también ocurre en tiempo constante. Los conjuntos también tienen más formas de eliminar elementos, de modo que no se generen errores o se puedan eliminar varios elementos de manera concisa.
#LIST
numbers = [1, 3, 4, 7, 8, 11]numbers.remove(4)
numbers.remove(5) #Raises ERROR as 5 is not in list
numbers.pop(0) #Deletes number at index 0, ie. 1
#SET
numbers = {1, 3, 4, 7, 8, 11}
numbers.remove(4)
numbers.remove(5) #Raises ERROR as 5 is not in set
numbers.discard(5) #Does not raise error if 5 is not in the set
numbers -= {1,2,3} #Performs set difference, ie. 1, 3 are discarded
Inserción
Agregar a una lista y agregar elementos a un conjunto son operaciones constantes; Sin embargo, agregar a un índice específico en una lista (.insert) conlleva tiempo adicional para mover elementos.
num_list = [1,2,3]
num_set = {1,2,3}num_list.append(4)
num_set.add(4)
num_list += [5,6,7]
num_set += {5,6,7}
Operaciones avanzadas de montaje.
Además, todas las operaciones matemáticas que se pueden realizar en conjuntos también se implementan en Python. Estas operaciones vuelven a llevar mucho tiempo si se realizan manualmente en una lista y, una vez más, se optimizan gracias al hash.
A = {1, 2, 3, 5, 8, 13}
B = {2, 3, 5, 7, 13, 17}# A n B
AintersectB = A & B
# A U B
AunionB = A | B
# A \ B
AminusB = A - B
# A U B - A n B or A Delta B
AsymmetricdiffB = A ^ B
Esto también incluye operadores de comparación, es decir, subconjuntos y superconjuntos propios y relajados. Estas operaciones nuevamente se ejecutan mucho más rápido que sus contrapartes de lista, ejecutándose en tiempo O(n), donde n es el mayor de los 2 conjuntos.
A <= B #A is a proper subset of B
A > B #A is a superset of B
Conjuntos congelados
Una última característica pequeña pero subestimada de Python es la conjunto congeladoque es esencialmente un archivo de sólo lectura o inmutable juntos. Estos proporcionan una mayor eficiencia de la memoria y pueden ser útiles en los casos en los que se prueba con frecuencia la pertenencia a tuplas.
doconclusión
La esencia del uso de conjuntos para mejorar el rendimiento se resume en el principio de optimización por reducción.
Las estructuras de datos como las listas tienen la mayor funcionalidad (están indexadas y son dinámicas), pero tienen el costo de una eficiencia comparativamente menor: en términos de velocidad y memoria. Identificar la funcionalidad esencial o no utilizada para determinar qué tipo de datos usar dará como resultado un código que se ejecuta más rápido y se lee mejor.
Todos los diagramas técnicos por autor.
