1. Planteamiento
Un sistema de anuncios tiene N candidatos, donde cada peso representa una probabilidad relativa de selección. A la inicialización le siguen millones de extracciones de elementos individuales, por lo que cada extracción debe ser cercana a O(1) mientras las actualizaciones de peso por lotes siguen siendo posibles. Diseña una tabla de alias y cubre pesos cero, errores de punto flotante y límites de números aleatorios.
2. Restricciones y aclaraciones
- Comienza con una extracción con reemplazo; el muestreo sin reemplazo y las actualizaciones de un solo peso son extensiones.
- Los pesos son no negativos y su suma debe ser positiva; un elemento con peso cero nunca debe ser seleccionado.
- El muestreador puede usar un entero uniforme y un real uniforme en
[0, 1). - La reconstrucción en
O(N)después de un lote de pesos es aceptable, pero una tabla antigua no puede representar pesos nuevos.
3. Enfoque principal
Escala cada peso a p_i = w_i * N / sum(w), cuyo promedio es 1. Mantén arreglos prob y alias de longitud N. Un casillero (bucket) se devuelve a sí mismo con probabilidad prob[i]; de lo contrario salta a alias[i]. Durante el preprocesamiento, coloca los valores menores a 1 en small y los valores mayores a 1 en large; empareja uno de cada lado, llena el casillero pequeño y devuelve la capacidad sobrante al casillero grande hasta que todos los casilleros estén completos.
El muestreo primero elige un casillero de manera uniforme y luego compara un real uniforme con prob[i]. El área total asignada a cada elemento original es igual a su probabilidad normalizada, por lo que su frecuencia a largo plazo es proporcional a su peso.
4. Implementación de referencia
build(weights):
n = len(weights)
scale = n / sum(weights)
scaled = [w * scale for w in weights]
prob = array(n)
alias = array(n)
small, large = [], []
for i, value in enumerate(scaled):
(small if value < 1 else large).append(i)
while small and large:
s = small.pop()
l = large.pop()
prob[s] = scaled[s]
alias[s] = l
scaled[l] -= 1 - scaled[s]
(small if scaled[l] < 1 else large).append(l)
for i in small + large:
prob[i] = 1
alias[i] = i
return prob, alias
sample(prob, alias, rng):
i = rng.uniform_int(0, len(prob))
return i if rng.uniform01() < prob[i] else alias[i]5. Complejidad y corrección
El preprocesamiento toma tiempo y espacio O(N). Cada muestra necesita una elección de casillero uniforme, una comparación y a lo sumo una búsqueda en el arreglo, por lo que es O(1). Limita (clamp) prob en [0, 1] tras el error residual de punto flotante; define el rango de enteros como semiabierto para que no se omita el último casillero.
La validación requiere más que unas pocas extracciones. Genera suficientes muestras, compara cada frecuencia observada con w_i / sum(w) y utiliza intervalos de confianza o una prueba de chi-cuadrada para detectar sesgos significativos. Reemplaza una tabla reconstruida de forma atómica para que un muestreador nunca observe una versión mezclada.
6. Preguntas de seguimiento y trampas
- Las tablas de alias se adaptan a distribuciones estáticas o actualizadas por lotes. Para cambios frecuentes de un solo peso, un árbol de Fenwick o un árbol de segmentos pueden ser una mejor opción.
- El desbordamiento del total antes de la normalización rompe las proporciones; utiliza mayor precisión o escala primero.
- “O(1)” excluye el costo de reconstrucción y no hace que el generador de números aleatorios sea gratuito.
- Un total de cero no define ninguna distribución. Recházalo en lugar de devolver cada elemento uniformemente.
7. Lecturas complementarias
Compara sumas de prefijos con búsqueda binaria, árboles de Fenwick, muestreo de reservorio y tablas de alias: las estructuras de prefijos admiten actualizaciones dinámicas con muestreo O(log N), los reservorios se adaptan a flujos de datos (streams) y las tablas de alias intercambian un preprocesamiento O(N) por extracciones O(1) de alto rendimiento.
8. Puntos de evaluación en entrevistas
Puede construir los casilleros pequeños y grandes
El candidato debe explicar cómo escalar los pesos a una capacidad promedio de 1 y mover la capacidad sobrante entre un casillero pequeño y uno grande.
Puede demostrar la probabilidad de muestreo
Debe mostrar cómo la selección uniforme de casilleros más un salto de alias le da a cada elemento su área total objetivo en lugar de simplemente recitar código.
Puede manejar casos numéricos y de frontera
Debe cubrir pesos cero, total cero, ajuste (clamping) de punto flotante, rangos aleatorios semiabiertos y reemplazo atómico de tablas.
Puede elegir la estructura de datos adecuada
Debe comparar el costo de reconstrucción por lotes con las actualizaciones dinámicas y saber cuándo usar un árbol de Fenwick o sumas de prefijos en lugar de tablas de alias.