Eficiencia computacional

01 · Punto de partida

Exacto no alcanza: tiene que rendir

¿Un millón de normales por segundo o por minuto? ¿Knuth con λ = 100? Varios métodos exactos compiten por la misma F y el ganador depende de N: el costo por muestra (uniformes + operaciones) y el preprocesamiento (tablas que se pagan una vez) deciden.

La regla de este tema: medir con cronómetro y contador, no con intuición. La intuición dice “menos código = más rápido”; el perfilador suele opinar otra cosa.

• ¿Qué cuesta cada método en uniformes por muestra?
• ¿Cuándo un preprocesamiento O(n) se paga solo?
• ¿Qué dice la tasa de aceptación del rechazo?
• ¿Cómo medir sin autoengañarse?

02 · Definición

Marginal, setup y tasa

Costo marginal: uniformes + flops por muestra aceptada. Setup: tablas (alias, CDF) o constantes (logaritmos) que se amortizan con N. Tasa de aceptación: fracción de intentos que sobreviven al rechazo; su inversa multiplica el costo.

03 · Anatomía

Medir, vectorizar y cachear

Medir con timeit

Repetir y tomar el mínimo (ruido del sistema), calentar antes, comparar en la misma máquina. Un solo cronómetro miente por GC y caché.

Vectorizar el bucle

Generar el bloque de U de una vez y operar en lote rinde 10–50× en Python puro→NumPy. El algoritmo es el mismo; el intérprete deja de estorbar.

Cachear constantes y sobrantes

Precomputar 1/λ, tablas y acumuladas; guardar la segunda normal del par (spare). Lo repetido se calcula una vez.

Costo aleatorio

Rechazo y Knuth gastan un N° aleatorio de U por muestra: dimensionar por la media (c, λ+1) más margen para colas.

04 · Dónde rinde cada uno

Del N chico al streaming

1. 1
   N enorme.

   Setup amortizado: alias, tablas y ziggurat reinan con millones de muestras.

2. 2
   Tiempo real.

   Costo marginal acotado y sin colas: Box-Muller con caché, nunca Knuth con λ = 200.

3. 3
   Didáctica.

   Suma-12 y bucles claros cuando N es chico y manda la legibilidad.

4. 4
   Puente a selección.

   Precisión + velocidad + simplicidad según el caso. (Tema 40)

05 · Representación en Python

Tres normales contra el cronómetro

Mismo N, tres métodos: tiempo mínimo de 3 pasadas y uniformes teóricos por Z.

import random
import math
import time

random.seed(350)
N = 20000

def t_min(f):
    ts = []
    for _ in range(3):
        t0 = time.perf_counter()
        f()
        ts.append(time.perf_counter() - t0)
    return min(ts)

t12 = t_min(lambda: [sum(random.random() for _ in range(12)) - 6.0
                     for _ in range(N)])
def bm():
    out = []
    while len(out) < N:
        u1 = max(random.random(), 1e-12)
        u2 = random.random()
        r = math.sqrt(-2*math.log(u1))
        t = 2*math.pi*u2
        out += [r*math.cos(t), r*math.sin(t)]
    return out
tbm = t_min(bm)
print("suma-12 (12 U):", round(t12, 3), "s")
print("Box-Muller (1 U):", round(tbm, 3), "s")
print("ratio:", round(t12/max(tbm, 1e-9), 1))

Box-Muller suele ganar por 3–8×: 12× menos uniformes pesan más que la trigonometría.

06 · Exploración

Laboratorio: cronómetro en tu navegador

Genera N normales con cada método y mide ms por 1000 Z (mínimo de 3 pasadas). Las barras se normalizan al más rápido. Repetilo: el orden es estable, los absolutos bailan con tu máquina.

Barras relativas al ganador. Probá N = 30000 (se estabiliza) y N = 2000 (ruido). Si ves <0,05 ms, el cronómetro no resuelve: subí N.

Preguntas para explorar

1. ¿Quién gana en tu máquina? ¿Por qué factor contra suma-12?
2. ¿Box-Muller o polar? ¿La brecha se achica con N grande?
3. Repetí la medición. ¿Cambian los absolutos? ¿Y el orden?

07 · Comprensión

Confusiones frecuentes

08 · Práctica guiada

Ejercicios con Python

Ejercicio 1: contar uniformes binomiales

Con n = 50, p = 0,3: la suma gasta 50 U por muestra; la inversión con tabla, 1. Verificá el factor 50×.

import random
import math

random.seed(351)
n, p, N = 50, 0.3, 2000
masa = [(1-p)**n]
for k in range(n):
    masa.append(masa[-1]*(n-k)/(k+1)*p/(1-p))
print("U/muestra suma:", n, "vs inversión: 1")
m = [sum(1 for _ in range(n) if random.random() < p) for _ in range(N)]
print("media:", round(sum(m)/N, 2), "vs", n*p)

Ejercicio 2: Knuth que se encarece

Medí Poisson por Knuth con λ = 2 y λ = 20: el tiempo debe escalar ≈ ×10 (λ+1 uniformes por muestra).

import random
import math
import time

def tknuth(lam, N):
    L = math.exp(-lam)
    t0 = time.perf_counter()
    for _ in range(N):
        k, q = 0, 1.0
        while True:
            q *= random.random()
            if q <= L:
                break
            k += 1
    return time.perf_counter() - t0

random.seed(352)
print("λ=2:", round(tknuth(2.0, 3000), 3))
random.seed(352)
print("λ=20:", round(tknuth(20.0, 3000), 3))

Ejercicio 3: vectorizar el remuestreo

Compará bucle Python contra comprensión para 100000 índices: la misma O(m) con distinta constante.

import random
import time

random.seed(353)
n, m = 100, 100000
t0 = time.perf_counter()
a = []
for _ in range(m):
    a.append(int(n*random.random()))
t1 = time.perf_counter()
b = [int(n*random.random()) for _ in range(m)]
t2 = time.perf_counter()
print("bucle:", round(t1-t0, 3), "vs compr.:", round(t2-t1, 3))

09 · Síntesis

Ideas para recordar

En el próximo tema la decisión: selección del método según el caso.