Algoritmos Aleatorizados y Hashing: Optimizando el Rendimiento a Través de la Probabilidad

El diseño de algoritmos suele centrarse en optimizar el rendimiento en el peor de los casos. No obstante, existe un método revolucionario que permite crear soluciones potentes relajando la exigencia de ser siempre correctas o siempre eficientes.

Este enfoque constituye el núcleo de los algoritmos aleatorizados y el hashing moderno.

1. Introducción a los Algoritmos Aleatorizados

Algoritmos Aleatorizados

Los algoritmos aleatorizados son procedimientos que utilizan la aleatoriedad (típicamente a través de lanzamientos de monedas o selección de números al azar) para guiar su proceso de ejecución.

En este contexto, cualquier rendimiento deficiente no se atribuye a una instancia de entrada adversa, sino a la mala suerte inherente al azar.

Propósito Central

Éxito

El objetivo principal es desarrollar algoritmos que:

Mantengan garantías de rendimiento
Eviten la complejidad de estructuras de datos engorrosas
Simplifiquen la implementación
Eliminen casos adversos del peor escenario

Características Generales

Ventajas:

✅ Simples de describir e implementar
✅ Evitan casos patológicos del peor caso
✅ Rendimiento esperado excelente
✅ Estructuras de datos más ligeras

Desafíos:

⚠️ Análisis riguroso notoriamente complejo
⚠️ Requiere teoría formal de probabilidad
⚠️ Necesidad de generadores de números aleatorios de calidad

2. Clasificación: Las Vegas vs Monte Carlo

Los algoritmos aleatorizados se clasifican según sus garantías:

Algoritmos Las Vegas

Las Vegas: Siempre Correctos

Garantizan la corrección de la salida, pero no siempre garantizan la eficiencia.

Lema: “Si termina, la respuesta es correcta. Pero puede tardar más de lo esperado.”

Ejemplo Clásico: Quicksort Aleatorizado

Quicksort Aleatorizado

import random

def quicksort_aleatorizado(arr):
"""
Quicksort con pivote aleatorio (Las Vegas)

    - Siempre produce un array ordenado (correcto)
    - Tiempo esperado: O(n log n)
    - Peor caso: O(n²) (extremadamente improbable)
    """
    if len(arr) <= 1:
        return arr

    # Selección ALEATORIA del pivote (clave del algoritmo)
    pivote = random.choice(arr)

    # Particionar
    menores = [x for x in arr if x < pivote]
    iguales = [x for x in arr if x == pivote]
    mayores = [x for x in arr if x > pivote]

    # Recursión
    return quicksort_aleatorizado(menores) + iguales + quicksort_aleatorizado(mayores)

# Ejemplo

numeros = [64, 34, 25, 12, 22, 11, 90, 88, 45, 50]
resultado = quicksort_aleatorizado(numeros)
print(f"Ordenado: {resultado}")

# Siempre correcto, independientemente de la secuencia de pivotes

¿Por qué funciona tan bien?

En Quicksort, el peor caso ocurre cuando siempre elegimos el peor pivote (el mínimo o máximo):


Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Si pivote = 1:
Menores: []
Iguales: [1]
Mayores: [2, 3, 4, 5, 6, 7, 8, 9, 10] ← Problema: 9 elementos

Si pivote = 10:
Menores: [1, 2, 3, 4, 5, 6, 7, 8, 9] ← Problema: 9 elementos
Iguales: [10]
Mayores: []

Con selección aleatoria:

La probabilidad de elegir consistentemente el peor pivote en cada nivel es aproximadamente:

$(2/n) \times (2/(n-1)) \times (2/(n-2)) \times ...$

Para $n = 10$ y 10 niveles, la probabilidad del peor caso es aproximadamente $1/10^{10} = 0.0000000001$

¡Una en diez mil millones!

Tiempo esperado:

Con pivotes aleatorios, en promedio obtenemos particiones “razonablemente balanceadas”:

Mejor caso: Pivote central → $T(n) = 2T(n/2) + O(n) = O(n \log n)$
Caso promedio: Pivote en el rango 25%-75% → $O(n \log n)$
Peor caso: Pivote extremo siempre → $O(n^2)$ (probabilidad negligible)

Resultado: $O(n \log n)$ con alta probabilidad.

Algoritmos Monte Carlo

Monte Carlo: Siempre Rápidos

Garantizan ser eficientes, pero solo suelen producir la respuesta correcta o una aproximación.

Lema: “Siempre termina rápido. Pero puede equivocarse (con baja probabilidad).”

Ejemplo Clásico: Prueba de Primalidad de Miller-Rabin

Prueba de Primalidad (Monte Carlo)

import random

def potencia_modular(base, exponente, modulo):
    """Calcula (base^exponente) % modulo eficientemente"""
    resultado = 1
    base = base % modulo

    while exponente > 0:
        if exponente % 2 == 1:
            resultado = (resultado * base) % modulo
        exponente = exponente >> 1
        base = (base * base) % modulo

    return resultado

def es_probablemente_primo(n, k=100):
    """
    Test de primalidad de Miller-Rabin (Monte Carlo)

    - Siempre rápido: O(k log³ n)
    - Puede dar falso positivo con probabilidad < 1/4^k
    - Con k=100, probabilidad de error < 1/2^200 (despreciable)
    """
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False

    # Escribir n-1 como 2^r * d
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2

    # Realizar k pruebas
    for _ in range(k):
        # Elegir testigo aleatorio
        a = random.randint(2, n - 2)
        x = potencia_modular(a, d, n)

        if x == 1 or x == n - 1:
            continue

        for _ in range(r - 1):
            x = potencia_modular(x, 2, n)
            if x == n - 1:
                break
        else:
            return False  # Definitivamente compuesto

    return True  # Probablemente primo

# Ejemplos
print(f"17 es primo: {es_probablemente_primo(17)}")      # True
print(f"561 es primo: {es_probablemente_primo(561)}")    # False (número de Carmichael)
print(f"104729 es primo: {es_probablemente_primo(104729)}")  # True

# Número grande
numero_grande = 2**127 - 1  # Primo de Mersenne
print(f"2^127 - 1 es primo: {es_probablemente_primo(numero_grande)}")  # True

Probabilidad de error:

El test de Miller-Rabin tiene la siguiente garantía:

Si $n$ es primo → siempre responde “primo” (✓)
Si $n$ es compuesto → responde “compuesto” con probabilidad $\geq 3/4$

Con $k$ pruebas independientes, la probabilidad de error es:

$P(error) \leq 1/4^k$

Ejemplos prácticos:

Pruebas $(k)$	Probabilidad de Error	Comparación
10	$1/4^{10} \approx 10^{-6}$	Una en un millón
20	$1/4^{20} \approx 10^{-12}$	Una en un billón
50	$1/4^{50} \approx 10^{-30}$	Una en mil nonillones
100	$1/4^{100} \approx 10^{-60}$	Menos probable que ganar la lotería 10 veces seguidas

Con $k=100$ (valor típico), la probabilidad de error es astronómicamente pequeña.

Comparación con errores físicos:

Error de hardware (bit flip): $\approx 10^{-17}$ por bit por segundo
Error de Miller-Rabin ( $k=100$ ): $< 10^{-60}$

¡Es más probable que tu computadora tenga un error de hardware que el algoritmo se equivoque!

Comparación Las Vegas vs Monte Carlo

Característica	Las Vegas	Monte Carlo
Corrección	✅ Siempre correcta	⚠️ Probabilísticamente correcta
Tiempo	⚠️ Puede variar	✅ Siempre rápido
Ejemplo	Quicksort aleatorizado	Prueba de primalidad
Uso típico	Cuando la corrección es crítica	Cuando la velocidad es crítica
Garantía	”Si termina, es correcto"	"Siempre termina rápido”

Quiz

¿Cuál es la diferencia fundamental entre algoritmos Las Vegas y Monte Carlo?

3. Hashing como Proceso Aleatorizado

Hashing Aleatorizado

El hashing tradicionalmente mapea claves a enteros de manera determinista. Cuando la función hash se selecciona al azar de una familia de funciones, se convierte en un proceso aleatorizado.

El Problema del Peor Caso Determinista

Adversario Malicioso

Para cualquier función hash determinista, un adversario puede construir un conjunto de claves que colisionen en el mismo cubo, degradando el rendimiento a $O(n)$ .

Ejemplo del ataque:

Ataque a una función hash determinista

# Función hash simple (determinista)
def hash_simple(clave, m=10):
    """Hash: suma de caracteres módulo m"""
    return sum(ord(c) for c in clave) % m

# Un adversario puede encontrar colisiones fácilmente

m = 10
tabla = [[] for \_ in range(m)]

# Claves diseñadas para colisionar

claves_maliciosas = [
"ab", "ba", # sum=195, 195 % 10 = 5
"cd", "dc", # sum=199, 199 % 10 = 9
"abc", "bac", "cab" # sum=294, 294 % 10 = 4
]

for clave in claves_maliciosas:
indice = hash_simple(clave, m)
tabla[indice].append(clave)
print(f"'{clave}' → cubo {indice}")

print(f"\nTabla hash:")
for i, cubo in enumerate(tabla):
if cubo:
print(f"Cubo {i}: {cubo} ({len(cubo)} elementos)")

# Resultado: Múltiples colisiones en cubos específicos

# Búsqueda degrada a O(n) en esos cubos

Hashing Universal: Selección Aleatoria

Solución: Hashing Universal

Propósito: Eliminar el problema de la instancia de entrada del peor caso seleccionando la función hash al azar de una familia de funciones.

Resultado: El rendimiento adverso se convierte en “mala suerte extrema” (como ganar la lotería).

Construcción de Funciones Hash Aleatorias

Si la función básica es $h(x) = f(x) \bmod m$ , se puede introducir aleatoriedad eligiendo un número primo grande $p$ al azar:

$h(x) = ((f(x) \bmod p) \bmod m)$

Esto proporciona garantías legítimas de aleatoriedad.

Hashing Universal - Implementación

import random

class HashUniversal:
    """
    Implementación de hashing universal
    Familia de funciones hash: h(x) = ((ax + b) mod p) mod m
    """
    def __init__(self, m, p=None):
        """
        m: Tamaño de la tabla hash
        p: Número primo grande (se genera si no se proporciona)
        """
        self.m = m

        # Generar primo grande si no se proporciona
        if p is None:
            self.p = self._generar_primo_grande()
        else:
            self.p = p

        # Seleccionar a y b ALEATORIAMENTE
        self.a = random.randint(1, self.p - 1)
        self.b = random.randint(0, self.p - 1)

        print(f"Función hash: h(x) = ((({self.a} * x + {self.b}) mod {self.p}) mod {self.m})")

    def _generar_primo_grande(self):
        """Genera un primo grande mayor que el tamaño de la tabla"""
        primos = [1009, 2003, 5003, 10007, 20011, 50021, 100003]
        return random.choice([p for p in primos if p > self.m * 10])

    def hash(self, x):
        """Aplicar la función hash universal"""
        if isinstance(x, str):
            # Convertir string a número
            x = sum(ord(c) * (256 ** i) for i, c in enumerate(x))

        return ((self.a * x + self.b) % self.p) % self.m

# Ejemplo: Dos instancias con funciones hash diferentes
print("=== Función Hash 1 (aleatorizada) ===")
hash1 = HashUniversal(m=10)

claves = ["alice", "bob", "charlie", "david", "eve"]
print("\nDistribución de claves:")
for clave in claves:
    indice = hash1.hash(clave)
    print(f"'{clave}' → cubo {indice}")

print("\n=== Función Hash 2 (diferente, aleatorizada) ===")
hash2 = HashUniversal(m=10)

print("\nDistribución de claves (mismas claves, función diferente):")
for clave in claves:
    indice = hash2.hash(clave)
    print(f"'{clave}' → cubo {indice}")

# Cada ejecución produce distribuciones diferentes
# El adversario no puede predecir dónde caerán las claves

Teorema de Hashing Universal:

Para una familia de funciones hash universal, la probabilidad de que dos claves distintas $x$ e $y$ colisionen es:

$P(h(x) = h(y)) \leq \frac{1}{m}$

Donde $m$ es el tamaño de la tabla hash.

Comparación:

Tipo de Hash	Colisiones en peor caso	Colisiones esperadas
Determinista	$n$ elementos en 1 cubo	Depende del adversario
Universal	Variable (aleatorio)	$\leq n/m$ por cubo

Ejemplo numérico:

Tabla de $m = 100$ cubos
$n = 200$ elementos insertados
Función hash universal

Colisiones esperadas en un cubo dado:

$E[colisiones] = n/m = 200/100 = 2$ elementos por cubo

Tiempo de búsqueda esperado:

Con factor de carga $\alpha = n/m$ , el tiempo esperado es $O(1 + \alpha)$

Para $\alpha < 1$ (tabla no sobrecargada), búsqueda en $O(1)$ esperado.

Quiz

¿Por qué el hashing universal previene ataques de un adversario?

4. Filtros de Bloom: Eficiencia Espacial Probabilística

Filtro de Bloom

Un Filtro de Bloom es una estructura de datos basada en un vector de bits, diseñada para probar la pertenencia a un conjunto de manera extremadamente eficiente en espacio.

Utiliza $k$ funciones hash diferentes para cada elemento.

Propósito Central

Éxito

Principal utilidad:

Conservar memoria masivamente (bits vs punteros)
Mantener baja probabilidad de falsos positivos
Aplicación crucial: servidores que buscan documentos duplicados (índices web)

Funcionamiento

Estructura:

Vector de $m$ bits (inicialmente todos en 0)
$k$ funciones hash independientes: $h_1, h_2, \ldots, h_k$
$n$ elementos insertados

Operaciones:

Insertar elemento $s$ :

Calcular $h_1(s), h_2(s), \ldots, h_k(s)$
Establecer bits en posiciones correspondientes a 1

Consultar si $s$ está presente:

Verificar bits en posiciones $h_1(s), h_2(s), \ldots, h_k(s)$
Si todos son 1 → “Probablemente presente”
Si alguno es 0 → “Definitivamente ausente”

Filtro de Bloom - Implementación

import hashlib

class FiltroBloom:
"""
Implementación de un Filtro de Bloom

    Características:
    - Ahorro masivo de espacio
    - Sin falsos negativos
    - Posibles falsos positivos (controlados)
    """
    def __init__(self, m, k):
        """
        m: Tamaño del vector de bits
        k: Número de funciones hash
        """
        self.m = m  # Tamaño del filtro
        self.k = k  # Número de funciones hash
        self.bits = [0] * m  # Vector de bits
        self.elementos_insertados = 0

    def _hash(self, item, seed):
        """Genera hash con semilla para simular k funciones diferentes"""
        h = hashlib.md5(f"{item}{seed}".encode())
        return int(h.hexdigest(), 16) % self.m

    def insertar(self, item):
        """Insertar elemento en el filtro"""
        for i in range(self.k):
            posicion = self._hash(item, i)
            self.bits[posicion] = 1
        self.elementos_insertados += 1

    def contiene(self, item):
        """
        Verificar si el elemento probablemente está en el conjunto

        Returns:
            True: Probablemente presente (puede ser falso positivo)
            False: Definitivamente ausente (100% seguro)
        """
        for i in range(self.k):
            posicion = self._hash(item, i)
            if self.bits[posicion] == 0:
                return False  # Definitivamente NO está
        return True  # Probablemente SÍ está

    def tasa_falsos_positivos(self):
        """Calcular probabilidad teórica de falsos positivos"""
        # p = (1 - e^(-kn/m))^k
        import math
        p = (1 - math.e ** ((-self.k * self.elementos_insertados) / self.m)) ** self.k
        return p

    def __repr__(self):
        bits_activos = sum(self.bits)
        return f"FiltroBloom(m={self.m}, k={self.k}, bits activos={bits_activos}/{self.m})"

# Ejemplo de uso

print("=== Filtro de Bloom para detección de URLs visitadas ===\n")

# Crear filtro: 1000 bits, 3 funciones hash

filtro = FiltroBloom(m=1000, k=3)

# Insertar URLs visitadas

urls_visitadas = [
"google.com",
"github.com",
"stackoverflow.com",
"wikipedia.org",
"reddit.com"
]

print("Insertando URLs visitadas...")
for url in urls_visitadas:
filtro.insertar(url)
print(f" ✓ {url}")

print(f"\n{filtro}")
print(f"Tasa de falsos positivos estimada: {filtro.tasa_falsos_positivos():.4%}\n")

# Consultas

print("=== Consultas ===")

# URLs que SÍ visitamos

print("\nURLs que SÍ visitamos:")
for url in ["google.com", "github.com"]:
resultado = filtro.contiene(url)
print(f" {url}: {'✓ Probablemente visitada' if resultado else '✗ No visitada'}")

# URLs que NO visitamos

print("\nURLs que NO visitamos:")
urls_no_visitadas = ["facebook.com", "twitter.com", "amazon.com"]
for url in urls_no_visitadas:
resultado = filtro.contiene(url)
if resultado:
print(f" {url}: ⚠️ Falso positivo!")
else:
print(f" {url}: ✓ Correctamente identificada como no visitada")

# Comparación de espacio

print("\n=== Comparación de Espacio ===")
print(f"Filtro de Bloom: {filtro.m} bits = {filtro.m // 8} bytes")
print(f"Tabla hash tradicional (50 bytes/URL): {len(urls*visitadas) * 50} bytes")
print(f"Ahorro: {(1 - (filtro.m // 8) / (len(urls*visitadas) * 50)) \* 100:.1f}%")

Advertencia: Falsos Positivos

Limitación Importante

Un Filtro de Bloom solo puede generar falsos positivos.

✅ Sin falsos negativos: Si dice “no está”, entonces definitivamente NO está
⚠️ Con falsos positivos: Si dice “está”, puede ser un falso positivo

Probabilidad de falsos positivos:

Después de insertar $n$ elementos en un filtro de $m$ bits usando $k$ funciones hash:

$P(FP) = (1 - e^{-kn/m})^k$

Optimización de $k$ :

La tasa de error se minimiza cuando:

$k_{optimo} = (m/n) \times \ln 2 \approx 0.693 \times (m/n)$

Tabla de tasas de error:

Supongamos $n = 10000$ elementos:

Bits por elemento $(m/n)$	$k$ óptimo	Tasa de falsos positivos
4	3	14.7%
8	6	2.1%
10	7	0.82%
12	8	0.33%
16	11	0.045%
20	14	0.006%

Observación crítica:

Existe un punto óptimo para $k$ . Más funciones hash no siempre es mejor:

$k$ muy pequeño → bits insuficientes establecidos → alta probabilidad de bits compartidos
$k$ muy grande → demasiados bits establecidos → el filtro se satura rápidamente

Ejemplo numérico:

Con $m = 10000$ bits, $n = 1000$ elementos, $k = 7$ :

$P(FP) = (1 - e^{-0.7})^7 \approx 0.008 = 0.8\%$

Solo 8 de cada 1000 consultas de elementos no presentes darán falsos positivos.

Aplicaciones Reales

Pro Tip

Casos de uso populares:

Navegadores web: Verificar URLs maliciosas sin descargar toda la base de datos
Bases de datos: Evitar búsquedas costosas en disco para claves que no existen
Caches: Verificación rápida antes de consultar cache lento
Blockchain: Bitcoin usa Filtros de Bloom para sincronización ligera
Sistemas distribuidos: Verificar duplicados sin comunicación costosa

Quiz

¿Cuál es la característica más importante de un Filtro de Bloom?

5. Hashing Mínimo (MinHash): Estimación de Similitud

MinHash

El hashing mínimo (MinHash) es un método que permite estimar la similitud entre dos documentos sin examinar todas sus palabras.

Se basa en seleccionar el hash de valor más pequeño entre todos los códigos hash de las palabras de un documento.

Propósito Central

Éxito

Objetivos:

Acelerar la búsqueda de similitud en grandes corpus
Facilitar el clustering de documentos a escala web
Estimar la similitud Jaccard eficientemente
Detectar duplicados y plagio en tiempo real

Similitud Jaccard

Definición: Similitud Jaccard

La similitud Jaccard entre dos conjuntos $A$ y $B$ es la razón entre la intersección y la unión:

$J(A, B) = |A \cap B| / |A \cup B|$

Valores entre 0 (completamente diferentes) y 1 (idénticos).

Procedimiento de MinHash

Proceso:

Representar cada documento como conjunto de palabras (o shingles)
Aplicar la misma función hash a cada palabra de ambos documentos
Registrar la palabra cuyo hash sea mínimo en $D_1$ (llamar minhash1)
Registrar la palabra cuyo hash sea mínimo en $D_2$ (llamar minhash2)

Teorema clave:

La probabilidad de que los minhashes coincidan es exactamente la similitud Jaccard:

$P(minhash1 = minhash2) = J(D_1, D_2)$

MinHash - Implementación

import hashlib
import random

class MinHash:
    """
    Implementación de MinHash para estimación de similitud
    """
    def __init__(self, num_hashes=100):
        """
        num_hashes: Número de funciones hash (más = mejor precisión)
        """
        self.num_hashes = num_hashes
        # Generar semillas aleatorias para cada función hash
        self.seeds = [random.randint(0, 2**32 - 1) for _ in range(num_hashes)]

    def _hash(self, item, seed):
        """Generar hash de un item con una semilla"""
        h = hashlib.md5(f"{item}{seed}".encode())
        return int(h.hexdigest(), 16)

    def calcular_minhash(self, conjunto):
        """
        Calcular la firma MinHash de un conjunto

        Returns: Lista de k valores hash mínimos
        """
        if not conjunto:
            return [float('inf')] * self.num_hashes

        signature = []
        for seed in self.seeds:
            # Para cada función hash, encontrar el hash mínimo
            min_hash = min(self._hash(item, seed) for item in conjunto)
            signature.append(min_hash)

        return signature

    def estimar_similitud(self, sig1, sig2):
        """
        Estimar similitud Jaccard comparando firmas MinHash

        Cuenta cuántas posiciones coinciden / total de posiciones
        """
        coincidencias = sum(1 for a, b in zip(sig1, sig2) if a == b)
        return coincidencias / len(sig1)

def tokenizar(texto):
    """Convertir texto en conjunto de palabras (lowercase)"""
    return set(texto.lower().split())

# Ejemplo de uso
print("=== MinHash para Detección de Similitud ===\n")

# Crear instancia de MinHash
minhash = MinHash(num_hashes=100)

# Documentos de ejemplo
doc1 = "el perro corre por el parque bajo el sol"
doc2 = "el gato camina por el parque bajo la luna"
doc3 = "el perro corre por el parque bajo el sol"  # Idéntico a doc1
doc4 = "programación en python es divertida y útil"

# Tokenizar documentos
conjunto1 = tokenizar(doc1)
conjunto2 = tokenizar(doc2)
conjunto3 = tokenizar(doc3)
conjunto4 = tokenizar(doc4)

print("Documentos:")
print(f"Doc1: {doc1}")
print(f"Doc2: {doc2}")
print(f"Doc3: {doc3}")
print(f"Doc4: {doc4}\n")

# Calcular firmas MinHash
sig1 = minhash.calcular_minhash(conjunto1)
sig2 = minhash.calcular_minhash(conjunto2)
sig3 = minhash.calcular_minhash(conjunto3)
sig4 = minhash.calcular_minhash(conjunto4)

# Calcular similitudes reales (Jaccard)
def jaccard_real(s1, s2):
    return len(s1 & s2) / len(s1 | s2)

# Comparaciones
print("=== Comparaciones ===\n")

comparaciones = [
    ("Doc1 vs Doc2", conjunto1, conjunto2, sig1, sig2),
    ("Doc1 vs Doc3", conjunto1, conjunto3, sig1, sig3),
    ("Doc1 vs Doc4", conjunto1, conjunto4, sig1, sig4),
    ("Doc2 vs Doc4", conjunto2, conjunto4, sig2, sig4),
]

for nombre, conj1, conj2, firma1, firma2 in comparaciones:
    jaccard_real_valor = jaccard_real(conj1, conj2)
    jaccard_estimado = minhash.estimar_similitud(firma1, firma2)
    error = abs(jaccard_real_valor - jaccard_estimado)

    print(f"{nombre}:")
    print(f"  Jaccard real:     {jaccard_real_valor:.3f}")
    print(f"  Jaccard estimado: {jaccard_estimado:.3f}")
    print(f"  Error:            {error:.3f}")
    print()

# Ahorro de espacio
print("=== Ahorro de Espacio ===")
print(f"Documento original: ~{len(doc1)} caracteres")
print(f"Firma MinHash: {len(sig1)} enteros = {len(sig1) * 4} bytes")
print(f"Reducción: {len(doc1) / (len(sig1) * 4):.1f}x más pequeño")

Problema: Estimar el número de valores distintos en un stream de datos usando memoria constante.

Solución con MinHash:

Estimación de valores distintos con MinHash

import hashlib

class ContadorDistintos:
"""
Estima el número de valores distintos en un stream
usando solo O(1) memoria (guardando el hash mínimo)
"""
def **init**(self, rango_hash=2\*\*32):
self.rango_hash = rango_hash
self.min_hash = float('inf')
self.elementos_vistos = 0

    def _hash(self, item):
        """Calcular hash de un item"""
        h = hashlib.md5(str(item).encode())
        return int(h.hexdigest(), 16) % self.rango_hash

    def procesar(self, item):
        """Procesar un elemento del stream"""
        h = self._hash(item)
        self.min_hash = min(self.min_hash, h)
        self.elementos_vistos += 1

    def estimar_distintos(self):
        """
        Estimar número de valores distintos

        Teoría: Si el hash mínimo es min_h, entonces
        estimación ≈ rango_hash / min_h
        """
        if self.min_hash == 0:
            return float('inf')

        return int(self.rango_hash / self.min_hash) - 1

# Ejemplo

print("=== Estimación de Valores Distintos en Stream ===\n")

contador = ContadorDistintos()

# Simular stream con repeticiones

stream = [1, 2, 3, 2, 4, 1, 5, 3, 6, 2, 7, 8, 1, 9, 10]
print(f"Stream: {stream}")
print(f"Elementos totales: {len(stream)}")

for item in stream:
contador.procesar(item)

valores_distintos_reales = len(set(stream))
valores_distintos_estimados = contador.estimar_distintos()

print(f"\nValores distintos reales: {valores_distintos_reales}")
print(f"Valores distintos estimados: {valores_distintos_estimados}")
print(f"Error: {abs(valores_distintos_reales - valores_distintos_estimados)}")

# La estimación mejora con streams más grandes

print("\n=== Stream más grande ===")
import random
stream*grande = [random.randint(1, 1000) for * in range(10000)]

contador2 = ContadorDistintos()
for item in stream_grande:
contador2.procesar(item)

distintos_reales = len(set(stream_grande))
distintos_estimados = contador2.estimar_distintos()

print(f"Stream de {len(stream_grande)} elementos")
print(f"Valores distintos reales: {distintos_reales}")
print(f"Valores distintos estimados: {distintos_estimados}")
print(f"Error relativo: {abs(distintos_reales - distintos_estimados) / distintos_reales \* 100:.1f}%")
print(f"\nMemoria usada: Solo 1 entero (el hash mínimo) ≈ 4 bytes")

Teoría:

Si tenemos $n$ valores distintos uniformemente distribuidos en un rango $M$ :

Hash mínimo esperado: $\approx M/n$
Por lo tanto: $n \approx M / min\_hash$

Ventaja: Solo necesitamos una variable (el hash mínimo) para estimar $n$ , sin importar cuántos elementos procesemos.

Quiz

¿Por qué funciona MinHash para estimar similitud Jaccard?

6. Generadores de Números Pseudo-Aleatorios

Pseudo-Aleatoriedad

Los generadores de números aleatorios empleados en algoritmos son típicamente pseudo-aleatorios: generan una salida predecible mediante un método determinista (como el método congruencial lineal).

Método Congruencial Lineal (LCG)

Información

Fórmula:

X_{n+1} = (a \cdot X_n + c) \bmod m

Donde:

$X_n$ = valor actual
$a$ = multiplicador
$c$ = incremento
$m$ = módulo
$X_0$ = semilla (seed)

Generador Congruencial Lineal

class GeneradorLCG:
    """
    Generador de números pseudo-aleatorios usando LCG
    X(n+1) = (a * X(n) + c) mod m
    """
    def __init__(self, semilla=12345):
        # Parámetros estándar (usados en glibc)
        self.a = 1103515245
        self.c = 12345
        self.m = 2**31
        self.actual = semilla

    def siguiente(self):
        """Generar siguiente número pseudo-aleatorio"""
        self.actual = (self.a * self.actual + self.c) % self.m
        return self.actual

    def siguiente_flotante(self):
        """Generar número en [0, 1)"""
        return self.siguiente() / self.m

    def siguiente_rango(self, minimo, maximo):
        """Generar número en [minimo, maximo]"""
        return minimo + int(self.siguiente_flotante() * (maximo - minimo + 1))

# Ejemplo
print("=== Generador Pseudo-Aleatorio (LCG) ===\n")

# Mismo seed → misma secuencia (predecible)
print("Generador 1 (seed=42):")
gen1 = GeneradorLCG(semilla=42)
secuencia1 = [gen1.siguiente_rango(1, 100) for _ in range(10)]
print(f"Secuencia: {secuencia1}")

print("\nGenerador 2 (seed=42, mismo seed):")
gen2 = GeneradorLCG(semilla=42)
secuencia2 = [gen2.siguiente_rango(1, 100) for _ in range(10)]
print(f"Secuencia: {secuencia2}")

print(f"\n¿Son idénticas? {secuencia1 == secuencia2}")

print("\nGenerador 3 (seed=999, diferente):")
gen3 = GeneradorLCG(semilla=999)
secuencia3 = [gen3.siguiente_rango(1, 100) for _ in range(10)]
print(f"Secuencia: {secuencia3}")

print(f"\n¿Son diferentes? {secuencia1 != secuencia3}")

# Distribución
print("\n=== Verificación de Distribución ===")
gen = GeneradorLCG()
numeros = [gen.siguiente_rango(1, 10) for _ in range(10000)]

from collections import Counter
frecuencias = Counter(numeros)

print("\nFrecuencias (esperado ≈ 1000 por número):")
for num in sorted(frecuencias.keys()):
    print(f"  {num}: {'█' * (frecuencias[num] // 50)} {frecuencias[num]}")

Suficiente para Algoritmos

Aunque los generadores pseudo-aleatorios son predecibles (deterministas), esta configuración es, por defecto, suficiente para que los algoritmos aleatorizados funcionen eficazmente.

Para criptografía se requieren generadores criptográficamente seguros (CSPRNG).

7. Cierre: Impacto de la Aleatoriedad en la Computación

Transformación del Diseño de Algoritmos

La introducción de la aleatoriedad transforma el diseño de algoritmos, ofreciendo:

✅ Eficiencia: Rendimiento esperado excelente
✅ Resiliencia: Elimina casos adversos del peor escenario
✅ Simplicidad: Estructuras de datos más ligeras
✅ Escalabilidad: Soluciones prácticas para problemas masivos

Ejemplos Clave Revisados

Algoritmo/Técnica	Tipo	Garantía	Complejidad	Aplicación
Quicksort Aleatorizado	Las Vegas	Siempre correcto	$O(n \log n)$ esperado	Ordenamiento
Prueba Primalidad (Miller-Rabin)	Monte Carlo	Siempre rápido	$O(k \log^3 n)$	Criptografía
Hashing Universal	Las Vegas	Sin colisiones adversas	$O(1)$ esperado	Tablas hash
Filtros de Bloom	Monte Carlo	Falsos positivos	$O(k)$ por operación	Detección duplicados
MinHash	Monte Carlo	Estimación similitud	$O(k \cdot n)$	Clustering, plagio

Lecciones Fundamentales

1. Relajar Garantías Absolutas

No siempre necesitamos ser perfectamente correctos o perfectamente rápidos. A menudo, “casi siempre correcto” o “rápido en promedio” es suficiente y mucho más simple.

2. Probabilidad vs Adversario

La aleatoriedad elimina la posibilidad de un adversario que construya el peor caso. En lugar de optimizar para el peor caso adverso, optimizamos para el caso típico aleatorio.

3. Trade-offs Espacio-Tiempo-Precisión

Estructuras como Filtros de Bloom y MinHash demuestran que podemos intercambiar:

Espacio masivo por pequeñas probabilidades de error
Precisión perfecta por velocidad y escalabilidad

4. Análisis Probabilístico

El análisis riguroso requiere teoría de probabilidad, pero las garantías son poderosas:

Probabilidades de error exponencialmente pequeñas
Rendimiento esperado predecible
Comportamiento robusto en práctica

5. Simplicidad de Implementación

Los algoritmos aleatorizados suelen ser más simples que sus contrapartes deterministas optimizadas:

Quicksort determinista optimizado:
  - Mediana de 3 o 5 elementos
  - Particionar en 3 vías
  - Cambiar a insertion sort para subarrays pequeños
  - 50+ líneas de código

Quicksort aleatorizado:
  - Elegir pivote al azar
  - Particionar estándar
  - Recursión simple
  - 15 líneas de código

6. Aplicaciones Prácticas Críticas

La aleatoriedad no es solo teórica - es fundamental en sistemas reales:

Google: MinHash para detección de duplicados web
Bitcoin: Proof-of-work aleatorizado
Bases de datos: Filtros de Bloom en Cassandra, BigTable
Criptografía: Generación de claves, protocolos seguros
Machine Learning: Gradient descent estocástico, dropout

Analogía Final

Analogía del Puente

Optimización del peor caso: Diseñar un puente para soportar el peor terremoto registrado en la historia.

Algoritmos aleatorizados: Construir el puente con materiales que, estadísticamente, fallarán en menos de 1 de cada mil millones de intentos aleatorios.

Aunque el fallo puede ocurrir, la probabilidad es tan pequeña que, para fines prácticos, se garantiza la seguridad y se logra una construcción mucho más simple y rápida.

Quiz

¿Cuál es la ventaja principal de los algoritmos aleatorizados sobre los deterministas?

Resumen de Conceptos Clave

Clasificación de Algoritmos Aleatorizados

Las Vegas:

✅ Siempre correcto
⚠️ Tiempo variable
Ejemplo: Quicksort aleatorizado

Monte Carlo:

✅ Siempre rápido
⚠️ Puede errar (baja probabilidad)
Ejemplo: Prueba de primalidad

Técnicas de Hashing

Hashing Universal:

Selección aleatoria de función hash
Elimina ataques adversarios
Búsqueda $O(1)$ esperado

Filtro de Bloom:

Vector de bits + $k$ funciones hash
Sin falsos negativos
Posibles falsos positivos (controlados)
Ahorro masivo de espacio

MinHash:

Estimación de similitud Jaccard
La probabilidad de que coincidan los minhashes es igual a la similitud: $P(match) = J(D_1, D_2)$
Aplicaciones: clustering, detección duplicados

Fórmulas Clave

Probabilidad de error (Monte Carlo con $k$ pruebas):

$P(error) \leq 1/4^k$

Falsos positivos (Filtro de Bloom):

$P(FP) = (1 - e^{-kn/m})^k$

LCG (generador pseudo-aleatorio): $X_{n+1} = (a \cdot X_n + c) \bmod m$

Aplicaciones Reales

Navegadores: Filtros de Bloom para URLs maliciosas
Bases de datos: Hashing universal, Bloom filters
Búsqueda web: MinHash para duplicados
Criptografía: Pruebas de primalidad
Machine Learning: Algoritmos estocásticos

Regla de Oro

“La aleatoriedad transforma casos adversos en mala suerte improbable”

Quiz

¿Qué estructura de datos sacrifica corrección perfecta por ahorro masivo de espacio?

¡Felicitaciones!

Has completado el estudio de Algoritmos Aleatorizados y Hashing. Ahora comprendes:

La diferencia entre algoritmos Las Vegas y Monte Carlo
Cómo la aleatoriedad elimina casos adversos del peor escenario
Hashing universal para prevenir ataques adversarios
Filtros de Bloom para eficiencia espacial con falsos positivos controlados
MinHash para estimación rápida de similitud
Generadores pseudo-aleatorios y su suficiencia práctica
Trade-offs entre espacio, tiempo, y precisión en estructuras probabilísticas

Próximo paso: Explorar algoritmos de grafos, programación dinámica avanzada, y técnicas de optimización combinatoria.

Explorar

Blog

Roadmaps

Algoritmos Aleatorizados y Hashing: Optimizando el Rendimiento a Través de la Probabilidad

1. Introducción a los Algoritmos Aleatorizados

Algoritmos Aleatorizados

Propósito Central

Éxito

Características Generales

2. Clasificación: Las Vegas vs Monte Carlo

Algoritmos Las Vegas

Las Vegas: Siempre Correctos

Algoritmos Monte Carlo

Monte Carlo: Siempre Rápidos

Comparación Las Vegas vs Monte Carlo

¿Cuál es la diferencia fundamental entre algoritmos Las Vegas y Monte Carlo?

3. Hashing como Proceso Aleatorizado

Hashing Aleatorizado

El Problema del Peor Caso Determinista

Adversario Malicioso

Hashing Universal: Selección Aleatoria

Solución: Hashing Universal

Construcción de Funciones Hash Aleatorias

¿Por qué el hashing universal previene ataques de un adversario?

4. Filtros de Bloom: Eficiencia Espacial Probabilística

Filtro de Bloom

Propósito Central

Éxito

Funcionamiento

Advertencia: Falsos Positivos

Limitación Importante

Aplicaciones Reales

Pro Tip

¿Cuál es la característica más importante de un Filtro de Bloom?

5. Hashing Mínimo (MinHash): Estimación de Similitud

MinHash

Propósito Central

Éxito

Similitud Jaccard

Definición: Similitud Jaccard

Procedimiento de MinHash

¿Por qué funciona MinHash para estimar similitud Jaccard?

6. Generadores de Números Pseudo-Aleatorios

Pseudo-Aleatoriedad

Método Congruencial Lineal (LCG)

Información

Suficiente para Algoritmos

7. Cierre: Impacto de la Aleatoriedad en la Computación

Transformación del Diseño de Algoritmos

Ejemplos Clave Revisados

Lecciones Fundamentales

Analogía Final

Analogía del Puente

¿Cuál es la ventaja principal de los algoritmos aleatorizados sobre los deterministas?

Resumen de Conceptos Clave

Clasificación de Algoritmos Aleatorizados

Técnicas de Hashing

Fórmulas Clave

Aplicaciones Reales

Regla de Oro

¿Qué estructura de datos sacrifica corrección perfecta por ahorro masivo de espacio?

¡Felicitaciones!