Hace unos días Marga estaba enfrascada en el desarrollo de una solución para web basada en JSON-RPC y surgió la frase, por parte del cliente (Nothmann Research): piensa en el !11. Cuando me lo comentó no lo entendí de primeras. El factorial de 11, ¿por qué?
La conversación se originó por el desarrollo de un servicio web. El desarrollo debía de contemplar el atender una petición simple con acceso a base de datos. El cliente solicitó además que se tuviese en cuenta la escalabilidad, es decir, que llegado el momento en el que se sucedan miles de peticiones de forma continuada, el controlar situaciones como: ¿soportaría la base de datos esas peticiones?, ¿qué tamaño podría alcanzar con el almacenaje de esas peticiones?, ¿podría seguir funcionando bien en caso de un gran crecimiento? ... piensa en !11.
Cuando se está desarrollando normalmente esto escapa al enfoque de desarrollo. El programador se basa en resolver un problema con una prueba simple y normalmente no cabe la preocupación de qué pasaría en caso de realizar ese tipo de peticiones de forma masiva y manteniendo este alto volumen en el tiempo. Esto me lleva a los problemas de la Facebook HackerCup. Cuando estuve participando en esta competición trataba de resolver los problemas de forma individualizada y sin ocuparme de qué pasaría en caso de que el rango o volumen de datos fuese 10 veces superior.
El problema de los píxeles muertos
En la edición de 2013, primera ronda, el ejercicio que daba más puntos para su resolución fue el de los Dead Pixels (píxeles muertos) que decía así:
Peter, el amigo de John, compró un monitor de alta resolución con dimensiones W x H, donde W es el número de píxeles en cada fila (el ancho) y H es el número de píxeles de cada columna (el alto). Sin embargo, hay N píxeles muertos en el monitor. El i-ésimo píxel muerto está colocado en (x[i], y[i]). (0, 0) es el primer píxel arriba a la izquierda y (W-1, H-1) es el último píxel situado abajo a la derecha. Las localizaciones de los píxeles muertos pueden ser generadas por 6 números enteros dados: X, Y, a, b, c y d; por las siguientes reglas. Si 2 píxeles están en la misma localización, son considerados el mismo. Es posible que haya menos de N píxeles muertos distintos. x[0] = X y[0] = Y x[i] = (x[i - 1] a + y[i - 1] b + 1) % W (for 0 < i < N) y[i] = (x[i - 1] c + y[i - 1] d + 1) % H (for 0 < i < N) Peter conecta su monitor a un ordenador y abre una imagen con dimensión P (ancho) x Q (alto). ¿Cuántas posiciones únicas puede ser situada la imagen para que pueda verse perfectamente (todos los píxeles de la imagen sean mostrados en el monitor)? La imagen no puede ser rotada.
Los datos de ejemplo que nos da el ejercicio para su resolución son de anchos de 4x4 hasta 14x15 y un máximo de píxeles muertos de 4. Si nos lanzamos a programar podremos realizar el algoritmo en un tiempo prudencial (depende de nuestra destreza) y teniendo en cuenta todas las premisas... ¿todas?
Antes de poner los datos de ejemplo nos dan una tabla de restricciones o reglas (constraints):
1 ≤ T ≤ 20 1 ≤ W, H ≤ 40 000 1 ≤ P ≤ W 1 ≤ Q ≤ H 1 ≤ N ≤ min(1 000 000, W * H) 1 ≤ a, b, c, d ≤ 100 0 ≤ X < W 0 ≤ Y < H
Si no reparamos en estos datos no nos daremos cuenta de que los datos de ejemplo del problema son valores entre 4 y 15 para el ancho de la pantalla, mientras que la restricción que podrían darnos como dato de entrada está entre 1 y 40.000, con posibilidad no de 4 píxeles muertos, sino de MIN(1.000.000, WxH).
En este caso, la resolución tiene otro elemento más a su enunciado de forma intrínseca: optimización. No debemos de buscar una solución. Debemos de buscar una solución que nos permita resolver cualquier combinación de datos dada en menos de 6 minutos (según el tiempo que nos da Facebook para subir el resultado junto con el código).
En caso de realizarlo por fuerza bruta tenemos un coste computacional de WxH = 1.600.000.000 de operaciones de comprobación. La comprobación es otro algoritmo que depende cómo se realice podría incrementar el tiempo de forma considerable.
Conclusiones
Este problema es de una competición de Facebook. Sin embargo, el programador se enfrenta a desafíos cada día aún sin saberlo muchas de las veces. A día de hoy, disponer de un código en un servidor para que cientos, miles o millones de personas puedan acceder a su contenido o incluso intentar explotarlo, hace necesario que no solo se realice el diseño y la implementación de nuestra solución para un problema concreto, sino además vigilar el rendimiento de estas soluciones que se ponen a disposición de todo el público en Internet.
Hasta a los más grandes les sucede esto: Github, Bitbucket, Google, Facebook, Whatsapp, LinkedIn, ... ¿y tu servicio?, ¿está preparado para soportar la carga que está por llegar?, ¿sabes cuál es tu índice anual de disponibilidad de servicio?
