Conjuntos y multiconjuntos

De qué trata este capítulo

Los dos capítulos anteriores construyeron una hash table y estudiaron su función hash. Este los pone a trabajar en las dos preguntas que más hacemos los programadores: "¿ya vi esto antes?" y "¿cuántos hay de cada uno?" Un conjunto es una hash table que guarda solo llaves, así que la membresía es O(1) y los duplicados son imposibles. Un multiconjunto guarda un conteo junto a cada llave, así que responde cuántas veces. Además de la membresía O(1), los conjuntos traen un álgebra —unión, intersección, diferencia— que convierte preguntas sobre colecciones enteras en una sola línea. Este capítulo construye ambos y muestra el patrón más útil de todo el libro: el conjunto de "vistos" que colapsa un ciclo O(n²) a O(n).

Un poco de historia

El conjunto es por mucho la idea más vieja de este libro: es décadas anterior a la computación. Georg Cantor fundó la teoría de conjuntos en los 1870s, y sus operaciones —unión, intersección y diferencia— son exactamente las que este capítulo implementa, sin cambios. Cuando los lenguajes de programación quisieron una estructura de datos para colecciones sin orden ni repetición, tomaron los conjuntos de Cantor casi al pie de la letra: el lenguaje SETL de los 1970s, diseñado por Jack Schwartz, hizo de los conjuntos un tipo de primera clase y demostró que podías escribir programas notablemente compactos pensando en operaciones de conjuntos. Python heredó ese linaje —su set y las comprensiones de conjuntos son descendientes de SETL— y el multiconjunto, la "bolsa" que permite repetición con un conteo, viene de la combinatoria, formalizado en esa misma tradición. Así que el álgebra tiene 150 años; lo único moderno es la implementación O(1) con hash table que va por debajo.

La intuición

Un conjunto es una bolsa a la que solo le puedes hacer una pregunta: ¿esto está dentro de ti? Como está respaldado por una hash table, la respuesta es O(1) —hasheas el elemento y revisas su bucket, sin recorrer nada—. Agregar un elemento que ya está no hace nada, y eso es justo lo que hace que un conjunto deduplique gratis: vacía una lista en un conjunto y los duplicados se colapsan.

El álgebra sale directo de la membresía O(1). La unión es "todo lo que esté en cualquiera de los dos": agregas ambos lados a un mismo conjunto. La intersección es "lo que está en ambos": recorres el conjunto más chico y te quedas con los elementos que el más grande también contiene, cada revisión O(1). La diferencia es "lo que está en mí pero no en ti". Las tres son baratas porque el "¿está X en este conjunto?" de abajo es barato. Un multiconjunto relaja la regla de no-duplicados guardando un conteo en vez de solo presencia, lo que lo vuelve la herramienta natural para llevar cuentas: frecuencias de palabras, votos, inventario.

Complejidad: cómo escala

La membresía, agregar y eliminar heredan el $O(1)$ promedio de la hash table: hasheas el elemento, tocas un bucket. Las operaciones de conjuntos se construyen sobre eso: la unión es $O(n + m)$ porque agrega cada elemento de ambos conjuntos; la diferencia es $O(n)$, una revisión de membresía por elemento del lado izquierdo; y la intersección es $O(\min(n, m))$ si tienes el cuidado de iterar el conjunto más chico y sondear el más grande, ya que cada sondeo es O(1). Ese detalle de "itera el más chico" importa: hazlo al revés y haces más trabajo para la misma respuesta. El espacio es $O(n)$.

La gráfica construye un conjunto, corre un lote de consultas de membresía y lo intersecta con otro —la carga de trabajo cotidiana de un conjunto— medido contra el set de Python:

Las dos líneas son rectas —trabajo total lineal, O(1) por operación— que es justamente la razón por la que los conjuntos son rápidos.

En qué es bueno y en qué no

Un conjunto es la herramienta correcta en el instante en que tu pregunta es sobre membresía o unicidad. Deduplicar, probar "¿está esto en la lista permitida?", encontrar qué comparten dos colecciones, llevar registro de qué ya visitaste: todo pasa a ser O(1) por elemento en vez de O(n). El multiconjunto extiende eso al conteo, que es su propio superpoder de todos los días. Estas están entre las estructuras que más se usan en código real, precisamente porque muchísimos problemas se reducen a "¿ya lo vi?" o "¿cuántos hay?".

Lo que un conjunto sacrifica es todo lo relacionado con orden y posición. No tiene primero ni último, no tiene índice, no tiene iteración ordenada, y descarta duplicados en silencio; así que si algo de eso te importa, el conjunto es la herramienta equivocada y lo que quieres es una lista o una estructura ordenada. Y como con todo lo que usa hashing, su O(1) es un promedio que descansa en un hash decente y un load factor acotado.

Los datos, o las entradas

El face-off construye conjuntos de enteros distintos, dispara un lote de consultas de membresía (mitad aciertos, mitad fallos) e intersecta dos conjuntos traslapados, ejercitando exactamente las operaciones de las que trata el capítulo. La animación usa dos conjuntos diminutos de seis elementos con un traslape de tres, para que puedas ver cómo se calcula una intersección, un sondeo de membresía a la vez.

Constrúyelo, una función a la vez

Agregar un elemento lo mete en su bucket, pero solo si no está ya ahí: un conjunto guarda cada elemento una sola vez:

def add(self, key):
    """O(1) average: put the key in its bucket, unless it's already there —
    a set holds each element at most once. Grow to keep buckets short."""
    bucket = self._buckets[self._index(key)]
    if key in bucket:
        return
    bucket.append(key)
    self._n += 1
    if self._n > 0.75 * self._cap:
        self._resize(self._cap * 2)

La membresía es la operación sobre la que se construye todo lo demás: una sola revisión de bucket en O(1):

def contains(self, key):
    """O(1) average: membership is a scan of just the key's bucket."""
    return key in self._buckets[self._index(key)]

def __contains__(self, key):
    return self.contains(key)

El álgebra entonces se lee casi igual que su definición matemática. La unión agrega ambos lados; la intersección recorre el conjunto más chico y se queda con lo que el más grande también tiene; la diferencia se queda con lo que al otro le falta:

def union(self, other):
    """O(n + m): every element in either set."""
    result = HashSet(self)
    for x in other:
        result.add(x)
    return result

def intersection(self, other):
    """O(min(n, m)): elements in both. Iterate the SMALLER set and probe the
    larger — each probe is O(1), so the total is bounded by the smaller size."""
    small, large = (self, other) if len(self) <= len(other) else (other, self)
    result = HashSet()
    for x in small:
        if x in large:
            result.add(x)
    return result

def difference(self, other):
    """O(n): elements in self but not in other."""
    result = HashSet()
    for x in self:
        if x not in other:
            result.add(x)
    return result

Y el multiconjunto cambia "está o no está" por un conteo, que es todo lo que hace falta para convertir un conjunto en un tablero de cuentas:

class Multiset:
    """A set that keeps counts — how many of each element. It's a hash table from
    element to count, so add/count/remove are all O(1) average."""

    def __init__(self, iterable=None):
        self._counts = {}
        if iterable is not None:
            for x in iterable:
                self.add(x)

    def add(self, key, n=1):
        self._counts[key] = self._counts.get(key, 0) + n

    def count(self, key):
        return self._counts.get(key, 0)

    def remove(self, key, n=1):
        if key in self._counts:
            self._counts[key] -= n
            if self._counts[key] <= 0:
                del self._counts[key]

    def most_common(self, k=None):
        items = sorted(self._counts.items(), key=lambda kv: -kv[1])
        return items[:k] if k is not None else items

    def __len__(self):
        return sum(self._counts.values())

Míralo funcionar

Aquí está una intersección calculada tal como lo hace el código: un sondeo de membresía a la vez. La fila de arriba es el conjunto A, la de abajo es B, y estamos calculando A ∩ B revisando cada elemento de A para ver si está en B. Naranja es el elemento que se está revisando; verde significa que está en ambos conjuntos (así que entra a la intersección); gris significa que solo está en A. Ve paso a paso: 1, 2 y 3 fallan, luego 4, 5 y 6 aciertan, cada acierto un sondeo O(1) dentro de B, no un recorrido. La intersección {4, 5, 6} se va armando conforme se encienden en verde las celdas de ambas filas:

El código completo

Las dos versiones en un mismo lugar; cambia entre ellas. La pestaña de la implementación desde cero tiene nuestro HashSet con su álgebra y el Multiset. La pestaña de la librería es lo que realmente usarías: set con los operadores |, & y -, y collections.Counter para el multiconjunto.

"""Sets and multisets — hash tables that answer the two most common questions in
programming: "have I seen this before?" and "how many of each?"

A set is a hash table that stores only keys, so membership is O(1). A multiset (or
"bag") keeps a count alongside each key, so it also answers how many times. On top
of O(1) membership, sets add an algebra — union, intersection, difference — that
turns whole-collection questions into a few lines.
"""


class HashSet:
    """A set on a chained hash table: keys only, O(1) membership on average."""

    def __init__(self, iterable=None, capacity=8):
        self._cap = capacity
        self._buckets = [[] for _ in range(capacity)]
        self._n = 0
        if iterable is not None:
            for x in iterable:
                self.add(x)

    def _index(self, key):
        return hash(key) % self._cap

    # region: add
    def add(self, key):
        """O(1) average: put the key in its bucket, unless it's already there —
        a set holds each element at most once. Grow to keep buckets short."""
        bucket = self._buckets[self._index(key)]
        if key in bucket:
            return
        bucket.append(key)
        self._n += 1
        if self._n > 0.75 * self._cap:
            self._resize(self._cap * 2)
    # endregion

    # region: contains
    def contains(self, key):
        """O(1) average: membership is a scan of just the key's bucket."""
        return key in self._buckets[self._index(key)]

    def __contains__(self, key):
        return self.contains(key)
    # endregion

    # region: remove
    def remove(self, key):
        """O(1) average: drop the key from its bucket if present."""
        bucket = self._buckets[self._index(key)]
        if key in bucket:
            bucket.remove(key)
            self._n -= 1
            return True
        return False
    # endregion

    def _resize(self, new_cap):
        old = self._buckets
        self._cap = new_cap
        self._buckets = [[] for _ in range(new_cap)]
        self._n = 0
        for bucket in old:
            for k in bucket:
                self.add(k)

    def __len__(self):
        return self._n

    def __iter__(self):
        for bucket in self._buckets:
            yield from bucket

    # region: setops
    def union(self, other):
        """O(n + m): every element in either set."""
        result = HashSet(self)
        for x in other:
            result.add(x)
        return result

    def intersection(self, other):
        """O(min(n, m)): elements in both. Iterate the SMALLER set and probe the
        larger — each probe is O(1), so the total is bounded by the smaller size."""
        small, large = (self, other) if len(self) <= len(other) else (other, self)
        result = HashSet()
        for x in small:
            if x in large:
                result.add(x)
        return result

    def difference(self, other):
        """O(n): elements in self but not in other."""
        result = HashSet()
        for x in self:
            if x not in other:
                result.add(x)
        return result
    # endregion


# region: multiset
class Multiset:
    """A set that keeps counts — how many of each element. It's a hash table from
    element to count, so add/count/remove are all O(1) average."""

    def __init__(self, iterable=None):
        self._counts = {}
        if iterable is not None:
            for x in iterable:
                self.add(x)

    def add(self, key, n=1):
        self._counts[key] = self._counts.get(key, 0) + n

    def count(self, key):
        return self._counts.get(key, 0)

    def remove(self, key, n=1):
        if key in self._counts:
            self._counts[key] -= n
            if self._counts[key] <= 0:
                del self._counts[key]

    def most_common(self, k=None):
        items = sorted(self._counts.items(), key=lambda kv: -kv[1])
        return items[:k] if k is not None else items

    def __len__(self):
        return sum(self._counts.values())
# endregion

"""Python's `set` is the hash set, and `collections.Counter` is the multiset —
both hash tables in C. `set` gives O(1) membership and the same union/intersection/
difference algebra (as the operators |, &, -); `Counter` keeps counts and adds
`most_common`.

So the face-off is our HashSet and Multiset against the built-ins they reimplement.
"""
from collections import Counter


# region: set_ops
def set_union(a, b):
    return set(a) | set(b)


def set_intersection(a, b):
    return set(a) & set(b)


def set_difference(a, b):
    return set(a) - set(b)
# endregion


# region: counter
def multiset_counter(iterable):
    """A Counter is a multiset: element -> count, with most_common built in."""
    return Counter(iterable)
# endregion

Desde cero vs. la librería

Misma estructura, mismas operaciones O(1), así que otra vez la diferencia es una constante, y bien grande, porque el nuestro es un hash set en Python haciendo en bytecode lo que set hace en C. Construir un conjunto de 160000 elementos, sondearlo e intersectarlo le tomó a nuestro HashSet unos 580 ms contra los 35 ms del set integrado: alrededor de 17 veces más lento. Ese es el impuesto ya conocido de reimplementar un contenedor central en Python, y es la razón por la que siempre usarías el integrado. El valor de construirlo es que las operaciones de conjuntos dejan de ser magia: cuando escribes a & b, ahora sabes que está recorriendo el conjunto más chico y sondeando el más grande, y sabes por qué intersectar un conjunto diminuto con uno enorme es barato mientras que unir dos enormes no lo es.

Dónde te lo vas a encontrar de verdad

Los conjuntos y multiconjuntos están en todas partes una vez que los volteas a ver. Toda deduplicación (list(set(xs))) es un conjunto. Cada recorrido de grafo y de árbol en este libro carga un conjunto de "visitados" para no reprocesar nodos. Las bases de datos usan operaciones de conjuntos para UNION, INTERSECT y DISTINCT. El control de acceso revisa si tus roles intersectan los roles requeridos. Los correctores ortográficos y el autocompletado prueban membresía en un diccionario. Y Counter —el multiconjunto— cuenta frecuencias de palabras, líneas de log, votos e inventario en una sola línea. Cada que un problema dice "único", "compartido", "ya visto" o "cuántos hay de cada uno", es un conjunto o un multiconjunto.

Puntos clave

Un conjunto es una hash table que guarda solo llaves: membresía O(1), sin duplicados, y un álgebra de unión, intersección y diferencia que se mantiene barata porque está construida sobre esa búsqueda O(1). Un multiconjunto guarda conteos en vez de mera presencia, lo que lo vuelve el contador natural. El patrón que debes llevarte a todas partes es el del conjunto de vistos: reemplazar "recorrer para revisar si ya vi esto" con una prueba de membresía O(1), lo que calladamente le quita un factor de n a más algoritmos que cualquier otro truco.

Con eso cierra el bloque de hashing: hash tables, funciones hash, y los conjuntos y conteos construidos sobre ellos. El hashing te compra O(1) al precio de perder todo el orden. El siguiente bloque cambia de tema por completo: recursión y ordenamiento, empezando por la idea que permite que un algoritmo se llame a sí mismo, y el call stack del capítulo cuatro que hace que funcione.