El algoritmo que se moría en CDMX: cómo pasé de O(10⁷) a una consulta en base de datos
Hace algunos años trabajé en un proyecto de marketing por teléfono. El objetivo era generar listas de números telefónicos válidos para hacer campañas de llamadas en distintas ciudades de México. Si en algún momento recibiste una de esas llamadas… lo siento. No fue personal.
El punto técnico del asunto era este: necesitábamos generar números de teléfono que fueran válidos según la regulación del IFT (Instituto Federal de Telecomunicaciones). Y para eso, construimos un algoritmo. Uno que funcionaba. Pero que a cierta escala, simplemente se moría.
Cómo funcionan los teléfonos en México (lo mínimo necesario)
En México, todos los números telefónicos tienen 10 dígitos. Lo interesante es que los primeros 2, 3 o 4 dígitos están asignados a una localidad y estado específicos según la numeración publicada por el IFT. Esto significa que si sabes en qué ciudad quieres operar, ya conoces una parte del número desde el inicio.
Pero el IFT no solo define los prefijos: también establece restricciones sobre qué combinaciones de dígitos son válidas. No todos los sufijos son permitidos. Hay reglas.
Así que el problema real era: dado un prefijo de ciudad, generar todas las combinaciones válidas de los dígitos restantes (entre 6 y 8 dígitos, dependiendo del prefijo), respetando las restricciones del regulador.
La primera versión: el infierno de los for
La implementación inicial fue lo más natural que se me ocurrió en ese momento: ciclos for anidados.
La lógica era directa: iterar sobre cada posición de dígito, generar todas las combinaciones posibles, y dentro de cada iteración aplicar los if con las reglas del IFT para filtrar las combinaciones inválidas.
En el peor caso —ciudades con prefijo de 3 dígitos, donde quedan 7 dígitos libres— la complejidad llegaba a O(10⁷), es decir, hasta 10 millones de iteraciones solo para generar las combinaciones, antes siquiera de aplicar los filtros.
Para ciudades pequeñas, funcionaba. Tardaba un rato, pero terminaba.
Para ciudades como CDMX o Monterrey, el proceso tardaba horas. Literalmente. Y en aquella época yo no tenía experiencia con servidores ni procesamiento distribuido, así que el script corría en local, peleando contra los límites de memoria y CPU de mi equipo.
El algoritmo era correcto. El problema era el enfoque.
El insight clave: el problema no era el algoritmo, era la herramienta
Llegó un momento en que me puse a pensar diferente. El cuello de botella no era la lógica de negocio —las reglas del IFT eran las mismas sin importar cómo las implementara—. El problema era que estaba usando un proceso iterativo para resolver algo que en realidad era un problema de combinación de conjuntos de datos.
Y los motores de bases de datos llevan décadas siendo increíblemente buenos para exactamente eso.
El cambio de mentalidad fue este:
En lugar de generar las combinaciones con código, ¿qué tal si modelo las reglas como datos y dejo que la base de datos haga el cruce?
La solución: tablas temporales + JOINs + bulk insert
El nuevo enfoque funcionó así:
1. Las reglas del IFT se convirtieron en tablas
En lugar de tener las restricciones codificadas en if dentro de los ciclos, las traduje a tablas (muchas veces temporales) en la base de datos. Cada tabla representaba los valores válidos para una posición de dígito, condicionados al estado y localidad seleccionados.
sql
-- Ejemplo simplificado
CREATE TEMPORARY TABLE digitos_validos_pos1 AS
SELECT valor
FROM reglas_ift
WHERE estado = 'CDMX'
AND posicion = 1;
Top comments (0)