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 usar set
Sección titulada «Cuándo NO usar set»- 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.