set y tablas hash
Un set es la tabla hash del capítulo anterior sin la columna de valores. Eso lo hace un 11 % más compacto por entrada y, sobre todo, le da una propiedad que ninguna otra estructura tiene: las operaciones de conjuntos se ejecutan en C, no en un bucle de Python.
En una línea
Sección titulada «En una línea»Un set responde «¿está?» en 30 nanosegundos y no promete ningún orden.
Los huecos y el factor de carga
Sección titulada «Los huecos y el factor de carga»La tabla se redimensiona cuando llega al 60 % de ocupación. Un set de 4 en 8 huecos está al límite: la quinta inserción duplica la tabla y reubica todo.
Ese 60 % es la razón de que un set de un millón de elementos ocupe más que un millón por 16 bytes por hueco: hay huecos vacíos de sobra para que el sondeo encuentre rápido. El coste es memoria; el beneficio, búsqueda constante.
| Estructura | Memoria | Por entrada |
|---|---|---|
dict |
36.1 KB | 36.9 B |
set |
32.2 KB | 32.8 B |
frozenset |
32.2 KB | 32.8 B |
python mediciones/02-11-coste.py
El álgebra se hace en C
Sección titulada «El álgebra se hace en C»| Forma | Tiempo |
|---|---|
a & b |
1.89 ms |
[x for x in a if x in b] |
2.94 ms |
python mediciones/02-05-07-dict-set-orden.py
Sólo 1,6 veces, y conviene entender por qué no es más: la comprensión también usa la búsqueda hash de b por elemento. La ventaja de & es que evita el intérprete por iteración y crea el resultado con el tamaño ya calculado.
Donde la diferencia es enorme es cuando una de las dos partes es una lista: x in lista es O(n) y a & set(lista) convierte el problema en O(n) total en lugar de O(n × m).
a = {1, 2, 3}b = {3, 4}
a | b # unióna & b # interseccióna - b # diferenciaa ^ b # diferencia simétricaa <= b # subconjuntofrozenset: el conjunto que puede ser clave
Sección titulada «frozenset: el conjunto que puede ser clave»Un set es mutable y por tanto no es hashable: no puede estar dentro de otro set ni ser clave de un dict. frozenset sí:
grupos = { frozenset({"ana", "luis"}): "equipo A", frozenset({"eva", "marco"}): "equipo B",}Es la forma canónica de usar una combinación de elementos como clave, sin importar el orden en que lleguen.
La trampa
Sección titulada «La trampa»Cuándo no aplica
Sección titulada «Cuándo no aplica»- Con pocos elementos. Por debajo de cien,
x in listaes más rápido porque no hay coste de construcción de la tabla. - Cuando el orden importa de verdad. Un
setpara recorrer en orden es un error de diseño; usa una lista o undict. - Cuando necesitas el valor asociado. Eso es un
dict, no unsetde tuplas. - Cuando los elementos no son hashables. Listas de listas, diccionarios, objetos mutables: no entran.
Ejercicio
Sección titulada «Ejercicio»Tienes dos listas de 50 000 correos y necesitas: (a) los que están en ambas, (b) los que sólo están en la primera, (c) los nuevos conservando el orden de llegada. Escribe las tres operaciones y di cuál es el coste de cada una.
Solución
viejos = [f"user{i}@mail.com" for i in range(5)]nuevos = [f"user{i}@mail.com" for i in range(3, 8)]print(len(viejos), len(nuevos))
conj_viejos = set(viejos)conj_nuevos = set(nuevos)
en_ambas = conj_viejos & conj_nuevos # (a)solo_viejos = conj_viejos - conj_nuevos # (b)nuevos_ordenados = [e for e in nuevos if e not in conj_viejos] # (c)Costes: construir los dos conjuntos es O(n + m); la unión (a) es O(n + m) y la diferencia (b) recorre el conjunto izquierdo, O(n); (c) es O(m) con búsqueda constante.
El detalle importante es (c): se recorre nuevos en orden y se consulta el conjunto, en lugar de hacer set(nuevos) - conj_viejos, que perdería el orden. El conjunto se usa como índice, no como resultado.
Si hiciera falta conservar duplicados dentro de nuevos, la comprensión los mantiene; el set no.
Referencias
Sección titulada «Referencias»- Ramalho, L. Fluent Python, 2ª ed. Capítulo 3: conjuntos y tablas hash.
- CPython 3.13:
Objects/setobject.c(set_add_entry, factor de carga). - Mediciones:
mediciones/02-05-07-dict-set-orden.py.
Capítulos relacionados
Sección titulada «Capítulos relacionados»- 05 ·
dictpor dentro: la misma tabla con valores. - 09 · Hashabilidad (Parte I): el contrato que un
setexige. - 10 ·
collectionscompleto:CounteryChainMapsobre estas bases.